stars/StarSim_artur.java

  1 import java.io.BufferedReader;
  2 import java.io.InputStreamReader;
  3 import java.util.HashMap;
  4 import java.util.LinkedList;
  5 import java.util.List;
  6 import java.util.StringTokenizer;
  7 
  8 public class StarSim_artur {
  9 
 10   static final int MAXN = 100100;
 11   static final long[] x = new long[MAXN], y = new long[MAXN], z = new long[MAXN];
 12 
 13   static int n;
 14   static long ksqr;
 15 
 16   public static void main(String[] args) throws Exception {
 17     BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 18 
 19     int[] dx = new int[] { 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
 20     int[] dy = new int[] { 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, -1, -1, -1 };
 21     int[] dz = new int[] { 1, 0, 1, -1, 0, 1, -1, 0, 1, -1, 0, 1, -1 };
 22 
 23     while (true) {
 24       StringTokenizer str = new StringTokenizer(in.readLine());
 25       n = Integer.valueOf(str.nextToken());
 26       int k = Integer.valueOf(str.nextToken());
 27       if (n == 0 && k == 0)
 28         break;
 29       ksqr = k * 1L * k;
 30 
 31       HashMap<Bucket, LinkedList<Integer>> buckets = new HashMap<Bucket, LinkedList<Integer>>();
 32       for (int i = 0; i < n; i++) {
 33         str = new StringTokenizer(in.readLine());
 34         x[i] = Long.parseLong(str.nextToken());
 35         y[i] = Long.parseLong(str.nextToken());
 36         z[i] = Long.parseLong(str.nextToken());
 37 
 38         Bucket b = new Bucket(x[i] / k, y[i] / k, z[i] / k);
 39         if (!buckets.containsKey(b))
 40           buckets.put(b, new LinkedList<Integer>());
 41         buckets.get(b).add(i);
 42       }
 43 
 44       int total = 0;
 45       Bucket q = new Bucket(0, 0, 0);
 46       for (Bucket p : buckets.keySet()) {
 47         List<Integer> list = buckets.get(p);
 48         for (int i : list)
 49           for (int j : list)
 50             if (j < i)
 51               total += within(i, j) ? 1 : 0;
 52             else
 53               break;
 54         for (int ind = 0; ind < dx.length; ind++) {
 55           q.i = p.i + dx[ind];
 56           q.j = p.j + dy[ind];
 57           q.k = p.k + dz[ind];
 58           if (buckets.containsKey(q))
 59             for (int i : list)
 60               for (int j : buckets.get(q))
 61                 if (i != j && within(i, j))
 62                   total++;
 63         }
 64       }
 65       System.out.println(total);
 66     }
 67   }
 68 
 69   static boolean within(int i, int j) {
 70     long k = ksqr;
 71 
 72     long dx = x[i] - x[j];
 73     k -= dx * dx;
 74     if (k <= 0)
 75       return false;
 76 
 77     long dy = y[i] - y[j];
 78     k -= dy * dy;
 79     if (k <= 0)
 80       return false;
 81 
 82     long dz = z[i] - z[j];
 83     k -= dz * dz;
 84     if (k <= 0)
 85       return false;
 86 
 87     return true;
 88   }
 89 
 90   static class Bucket {
 91     long i, j, k;
 92 
 93     Bucket(long x, long y, long z) {
 94       i = x;
 95       j = y;
 96       k = z;
 97     }
 98 
 99     public int hashCode() {
100       final int prime = 31;
101       int result = 1;
102       result = prime * result + (int) (i ^ (i >>> 32));
103       result = prime * result + (int) (j ^ (j >>> 32));
104       result = prime * result + (int) (k ^ (k >>> 32));
105       return result;
106     }
107 
108     public boolean equals(Object obj) {
109       if (this == obj)
110         return true;
111       if (obj == null)
112         return false;
113       if (getClass() != obj.getClass())
114         return false;
115       Bucket other = (Bucket) obj;
116       if (i != other.i)
117         return false;
118       if (j != other.j)
119         return false;
120       if (k != other.k)
121         return false;
122       return true;
123     }
124   }
125 }