stars/StarSim_zeil.java
1
2 import java.io.BufferedReader;
3 import java.io.FileNotFoundException;
4 import java.io.FileReader;
5 import java.util.ArrayList;
6 import java.util.HashMap;
7 import java.util.Scanner;
8
9 public class StarSim_zeil {
10
11
12 public static class Point {
13 public int x, y, z;
14
15 public Point (int xx, int yy, int zz)
16 {
17 x = xx;
18 y = yy;
19 z = zz;
20 }
21
22 public String toString ()
23 {
24 return "(" + x + "," + y + "," + z + ")";
25 }
26
27 public int hashCode() {
28 return x + 1299 * y + 37 * z;
29 }
30
31 public boolean equals (Object obj)
32 {
33 Point p = (Point)obj;
34 return x == p.x && y == p.y && z == p.z;
35 }
36
37 public long distanceSq (Point p) {
38 long dx = x - p.x;
39 long dy = y - p.y;
40 long dz = z - p.z;
41 return dx*dx + dy*dy + dz*dz;
42 }
43 };
44
45 private static int setNumber = 0;
46
47 private int K;
48 private int N;
49 private Point[] points;
50 private HashMap<Point, ArrayList<Point>> hash;
51 int xmin, xmax;
52 int ymin, ymax;
53 int zmin, zmax;
54
55 int longestCell;
56
57
58 public long rangeSearch (Point center)
59 {
60 long counter = 0;
61 Point cell = selectCellFor (center);
62 long Ksq = (long)K * (long)K;
63 for (int dx = -1; dx <= 1; ++dx)
64 for (int dy = -1; dy <= 1; ++dy) {
65 for (int dz = -1; dz <= 1; ++dz) {
66 Point nearByCell = new Point(cell.x + dx, cell.y + dy, cell.z + dz);
67 ArrayList<Point> nearByPoints = hash.get(nearByCell);
68 if (nearByPoints != null) {
69 for (Point p: nearByPoints) {
70 double dist = p.distanceSq(center);
71 double diff = dist - Ksq;
72 if (diff < 0.0) {
73
74 ++counter;
75 }
76 }
77 }
78 }
79 }
80 --counter;
81 return counter;
82 }
83
84 private Point selectCellFor(Point p) {
85 int ix = (int)((p.x - xmin) / K);
86 int iy = (int)((p.y - ymin) / K);
87 int iz = (int)((p.z - zmin) / K);
88 return new Point(ix, iy, iz);
89 }
90
91
92
93 public StarSim_zeil(int n, Scanner in) {
94 N = n;
95 points = new Point[n];
96 hash = new HashMap<>();
97 xmin = ymin = zmin = Integer.MAX_VALUE;
98 xmax = ymax = zmax = Integer.MIN_VALUE;
99 longestCell=0;
100 K = in.nextInt();
101 for (int i = 0; i < n; ++i) {
102 int x = in.nextInt();
103 int y = in.nextInt();
104 int z = in.nextInt();
105 Point p = new Point(x,y,z);
106 points[i] = p;
107 xmin = Math.min(xmin, x);
108 xmax = Math.max(xmax, x);
109 ymin = Math.min(ymin, y);
110 ymax = Math.max(ymax, y);
111 zmin = Math.min(zmin, z);
112 zmax = Math.max(zmax, z);
113 }
114 }
115
116
117
118
119 public static void main (String[] args) throws FileNotFoundException
120 {
121 Scanner in;
122 if (args.length == 0)
123 in = new Scanner (System.in);
124 else
125 in = new Scanner(new BufferedReader(new FileReader(args[0])));
126 while (in.hasNextInt()) {
127 int n = in.nextInt();
128 if (n <= 0)
129 break;
130 new StarSim_zeil(n, in).solve();
131 ++setNumber;
132 }
133 }
134
135 private void solve() {
136 for (Point p: points) {
137 Point cell = selectCellFor(p);
138 ArrayList<Point> ptsInCell = hash.get(cell);
139 if (ptsInCell == null) {
140 ptsInCell = new ArrayList<>();
141 hash.put(cell, ptsInCell);
142 }
143 ptsInCell.add(p);
144 longestCell = Math.max(longestCell, ptsInCell.size());
145 }
146 long counter = 0;
147 for (Point p: points) {
148 counter += rangeSearch(p);
149 }
150
151 System.out.println(counter / 2L);
152
153
154 }
155
156
157 }