Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Question 2
- import java.io.*;
- import java.util.*;
- public class a {
- private static class State implements Comparable<State> {
- private long x;
- private long y;
- private int time;
- public State(long x, long y, int time) {
- this.x = x;
- this.y = y;
- this.time = time;
- }
- public int compareTo(State a) {
- return this.time - a.time;
- }
- }
- static boolean innocent(State grazing, State alibi) {
- long d1 = Math.abs(grazing.x - alibi.x);
- long d2 = Math.abs(grazing.y - alibi.y);
- long d3 = Math.abs(grazing.time - alibi.time);
- return (d1 * d1 + d2 * d2) > (d3 * d3);
- }
- public static void main(String[] args) throws IOException {
- // BufferedReader br = new BufferedReader(new FileReader("test.in"));
- // PrintWriter out = new PrintWriter(new File("test.out"));
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- StringTokenizer st = new StringTokenizer(br.readLine());
- int g = Integer.parseInt(st.nextToken());
- int n = Integer.parseInt(st.nextToken());
- ArrayList<State> grazings = new ArrayList<State>();
- for(int i = 0; i < g; i++) {
- st = new StringTokenizer(br.readLine());
- int x = Integer.parseInt(st.nextToken());
- int y = Integer.parseInt(st.nextToken());
- int t = Integer.parseInt(st.nextToken());
- grazings.add(new State(x, y, t));
- }
- ArrayList<State> alibis = new ArrayList<State>();
- for(int i = 0; i < n; i++) {
- st = new StringTokenizer(br.readLine());
- int x = Integer.parseInt(st.nextToken());
- int y = Integer.parseInt(st.nextToken());
- int t = Integer.parseInt(st.nextToken());
- alibis.add(new State(x, y, t));
- }
- Collections.sort(grazings);
- int numInnocent = 0;
- for(State alibi: alibis) {
- int lower = 0;
- int upper = g - 1;
- while(lower != upper) {
- int mid = (lower + upper + 1)/2;
- if(grazings.get(mid).time <= alibi.time) {
- lower = mid;
- }
- else {
- upper = mid - 1;
- }
- }
- State grazing = grazings.get(lower);
- boolean grazing1Check = innocent(grazing, alibi);
- lower = 0;
- upper = g-1;
- while(lower != upper) {
- int mid = (lower + upper)/2;
- if(grazings.get(mid).time >= alibi.time) {
- upper = mid;
- }
- else {
- lower = mid + 1;
- }
- }
- grazing = grazings.get(lower);
- boolean grazing2Check = innocent(grazing, alibi);
- if(grazing1Check || grazing2Check) {
- numInnocent++;
- }
- }
- System.out.println(numInnocent);
- // out.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement