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 								//if (!center.equals(p)) 	System.err.println (center +     + p);
 74 								++counter;
 75 							}
 76 						}
 77 					}
 78 				}
 79 			}
 80 		--counter; // because (center,center) does not count
 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 		/*System.err.println ( Test set   + setNumber +   N=  + N +    K=  + K
153 				+      longest cell=  + longestCell);*/
154 	}
155 	
156 	
157 }