Advertisement
a_chn

Untitled

Feb 19th, 2024
788
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.12 KB | None | 0 0
  1. // Question 2
  2. import java.io.*;
  3. import java.util.*;
  4.  
  5. public class a {
  6.  
  7.     private static class State implements Comparable<State> {
  8.         private long x;
  9.         private long y;
  10.         private int time;
  11.  
  12.         public State(long x, long y, int time) {
  13.             this.x = x;
  14.             this.y = y;
  15.             this.time = time;
  16.         }
  17.  
  18.         public int compareTo(State a) {
  19.             return this.time - a.time;
  20.         }
  21.     }
  22.  
  23.     static boolean innocent(State grazing, State alibi) {
  24.         long d1 = Math.abs(grazing.x - alibi.x);
  25.         long d2 = Math.abs(grazing.y - alibi.y);
  26.         long d3 = Math.abs(grazing.time - alibi.time);
  27.         return (d1 * d1 + d2 * d2) > (d3 * d3);
  28.     }
  29.  
  30.     public static void main(String[] args) throws IOException {
  31.         // BufferedReader br = new BufferedReader(new FileReader("test.in"));
  32.         // PrintWriter out = new PrintWriter(new File("test.out"));
  33.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  34.         StringTokenizer st = new StringTokenizer(br.readLine());
  35.  
  36.         int g = Integer.parseInt(st.nextToken());
  37.         int n = Integer.parseInt(st.nextToken());
  38.  
  39.         ArrayList<State> grazings = new ArrayList<State>();
  40.  
  41.         for(int i = 0; i < g; i++) {
  42.             st = new StringTokenizer(br.readLine());
  43.             int x = Integer.parseInt(st.nextToken());
  44.             int y = Integer.parseInt(st.nextToken());
  45.             int t = Integer.parseInt(st.nextToken());
  46.             grazings.add(new State(x, y, t));
  47.         }
  48.  
  49.         ArrayList<State> alibis = new ArrayList<State>();
  50.  
  51.         for(int i = 0; i < n; i++) {
  52.             st = new StringTokenizer(br.readLine());
  53.             int x = Integer.parseInt(st.nextToken());
  54.             int y = Integer.parseInt(st.nextToken());
  55.             int t = Integer.parseInt(st.nextToken());
  56.             alibis.add(new State(x, y, t));
  57.         }
  58.  
  59.         Collections.sort(grazings);
  60.  
  61.         int numInnocent = 0;
  62.  
  63.         for(State alibi: alibis) {
  64.             int lower = 0;
  65.             int upper = g - 1;
  66.             while(lower != upper) {
  67.                 int mid = (lower + upper + 1)/2;
  68.                 if(grazings.get(mid).time <= alibi.time) {
  69.                     lower = mid;
  70.                 }
  71.                 else {
  72.                     upper = mid - 1;
  73.                 }
  74.             }
  75.  
  76.             State grazing = grazings.get(lower);
  77.             boolean grazing1Check = innocent(grazing, alibi);
  78.  
  79.             lower = 0;
  80.             upper = g-1;
  81.             while(lower != upper) {
  82.                 int mid = (lower + upper)/2;
  83.                 if(grazings.get(mid).time >= alibi.time) {
  84.                     upper = mid;
  85.                 }
  86.                 else {
  87.                     lower = mid + 1;
  88.                 }
  89.             }
  90.  
  91.             grazing = grazings.get(lower);
  92.             boolean grazing2Check = innocent(grazing, alibi);
  93.  
  94.             if(grazing1Check || grazing2Check) {
  95.                 numInnocent++;
  96.             }
  97.         }
  98.  
  99.         System.out.println(numInnocent);
  100.         // out.close();
  101.     }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement