stars/stars_vanb.java
1
2 import java.io.*;
3 import java.util.*;
4 import java.awt.geom.*;
5
6
7
8
9
10
11 public class stars_vanb
12 {
13 public Scanner sc;
14 public PrintStream ps;
15
16 public class Star
17 {
18 public long x, y, z;
19 public Star( long x, long y, long z )
20 {
21 this.x=x; this.y=y; this.z=z;
22 }
23
24 public long d2( Star s )
25 {
26 long dx = x-s.x;
27 long dy = y-s.y;
28 long dz = z-s.z;
29
30 return dx*dx + dy*dy + dz*dz;
31 }
32 }
33
34 public HashMap<String,List<Star>> bins = new HashMap<String,List<Star>>();
35
36 public int dx[] = { 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1 };
37 public int dy[] = { 0, 1, 0, 1, 0, 1, 1, -1, 0, 1, 1, -1, -1 };
38 public int dz[] = { 0, 0, 1, 0, 1, 1, 1, 0, -1, -1, -1, 1, -1 };
39
40 public static String bin( long i, long k )
41 {
42 long b = i<0 ? ((i+1)/k-1) : i/k;
43 return ""+b;
44 }
45
46
47
48
49 public void doit() throws Exception
50 {
51 sc = new Scanner( new File( "stars.judge" ) );
52 ps = System.out;
53
54 for(;;)
55 {
56 int n = sc.nextInt();
57 long k = sc.nextLong();
58 if( n==0 ) break;
59
60 bins.clear();
61 for( int i=0; i<n; i++ )
62 {
63 long x = sc.nextLong();
64 long y = sc.nextLong();
65 long z = sc.nextLong();
66
67 String key = bin(x,k) + ":" + bin(y,k) + ":" + bin(z,k);
68 List<Star> stars = bins.get( key );
69 if( stars==null )
70 {
71 stars = new LinkedList<Star>();
72 bins.put( key, stars );
73 }
74 stars.add( new Star( x, y, z ) );
75 }
76
77 long kk = k*k;
78 int count = 0;
79 String keys[] = (String[])bins.keySet().toArray( new String[bins.keySet().size()] );
80 for( String key : keys )
81 {
82 List<Star> bin = bins.get( key );
83 Star local[] = (Star[])bin.toArray( new Star[bin.size()] );
84 for( int i=0; i<local.length; i++ ) for( int j=i+1; j<local.length; j++ )
85 {
86 if( local[i].d2( local[j] ) < kk ) ++count;
87 }
88 String tokens[] = key.split( ":" );
89 int kx = Integer.parseInt( tokens[0] );
90 int ky = Integer.parseInt( tokens[1] );
91 int kz = Integer.parseInt( tokens[2] );
92
93 for( int i=0; i<dx.length; i++ )
94 {
95 String newkey = "" + (kx+dx[i]) + ":" + (ky+dy[i]) + ":" + (kz+dz[i]);
96 List<Star> newbin = bins.get( newkey );
97 if( newbin!=null )
98 {
99 for( Star star1 : bin ) for( Star star2 : newbin )
100 {
101 if( star1.d2( star2 ) < kk ) ++count;
102 }
103 }
104 }
105 }
106
107 ps.println( count );
108 }
109 }
110
111
112
113
114 public static void main( String[] args ) throws Exception
115 {
116 new stars_vanb().doit();
117 }
118 }