stars/stars_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Star Simulations
  8  * 
  9  * @author vanb
 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      * Driver.
 47      * @throws Exception
 48      */
 49     public void doit() throws Exception
 50     {
 51         sc = new Scanner( new File( "stars.judge" ) );
 52         ps = System.out; //new PrintStream( new FileOutputStream(  stars.solution  ) );
 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      * @param args
113      */
114     public static void main( String[] args ) throws Exception
115     {
116         new stars_vanb().doit();         
117     }   
118 }