problem3.java

最近点对的随机算法 算法时间达到O(n)非常完美的实现了随机最近点对的功能

import java.util.Scanner;
import java.math.*;


public class problem3 {

static int n=0;
static double [] X = new double [1001];
static double [] Y = new double [1001];  
 
 static double dist(int a, int b){  
 return Math.sqrt((X[a]-X[b])*(X[a]-X[b])+(Y[a]-Y[b])*(Y[a]-Y[b]));  
 
 }

 public static void main(String[] args) {

               Scanner sc = new Scanner(System.in);
               n = sc.nextInt();
               int a=1;
               while (sc.hasNext()) {
			X[a] = sc.nextDouble();
                        Y[a++] = sc.nextDouble();
	        }
		sc.close();
               for (int c=1;c<=n;c++){
                     System.out.print(X[c]+" ");
               }
               System.out.println(" ");
               for (int c=1;c<=n;c++){
                     System.out.print(Y[c]+" ");
               }
               int sqrtn = (int)Math.sqrt(n);
               int [] array = new int [500];
               int [] temp = new int[sqrtn+1];
               int tempsize=0;
               int ii=1;
               for (ii=1;ii<=sqrtn;ii++){
                  int b= (int)(1+Math.random()*(n)); 
                  if (tempsize==0){
                      tempsize++;
                      temp[1] = b;
                       System.out.print("b="+b);
                         array[ii]=b;
                         continue;
                  }
                  for (int k=1;k<=tempsize;k++){
                   if(temp[k] == b){
                          ii--;
                        System.out.print("ii="+ii);
                          break;
                   }
                   else if (k!= tempsize )  continue;
                   else {
                     tempsize++;
                     temp[tempsize] = b; 
                     System.out.print("b="+b);
                     array[ii]=b;
                     break;
                   }
                   }
               }
               double min=90000;
               for(int i1=1;i1<=sqrtn;i1++){ //求根号N个点只间最短距离
                      for(int j1=i1+1;j1<=sqrtn;j1++){
                           if(dist(array[i1],array[j1])<min){
                              min = dist(array[i1],array[j1]) ;
                           }
                       }
               }
                System.out.print("min="+min);  
  System.out.println(" ");  
               double minx=90000;
                for (int i1=1;i1<=n;i1++){
                             if(X[i1]<minx)
                                      minx= X[i1];
                }
                System.out.println("minx="+minx);
                 double miny=90000;
                for (int i1=1;i1<=n;i1++){
                             if(Y[i1]<miny)
                                      miny= Y[i1];
                }
                System.out.println("miny="+miny);
                double maxx=-90000;
                double maxy=-90000;
                for (int i1=1;i1<=n;i1++){
                             if(X[i1]>maxx)
                                      maxx= X[i1];
                }
                System.out.println("maxx="+maxx);
                for (int i1=1;i1<=n;i1++){
                             if(Y[i1]>maxy)
                                      maxy= Y[i1];
                }
                System.out.println("maxy="+maxy);
                  
                  int c=10;                                  //算法里面的C
                int m= 0;
                int r=0;
                m=(int)((maxx-minx)/min+1);
                r=(int)((maxy-miny)/min+1);
                int [][][] cmr = new int[r+1][m+1][n+1];                 //list 连表！！！
                for (int i=1;i<=n;i++ ){
                    cmr[(int)((Y[i]-miny)/min+1)][(int)((X[i]-minx)/min+1)][0]++;
                    cmr[(int)((Y[i]-miny)/min+1)][(int)((X[i]-minx)/min+1)][cmr[(int)((Y[i]-miny)/min+1)][(int)((X[i]-minx)/min+1)][0]]=i;
                }//把点分配到cmr里面
               
                 for(int o=1;o<=r;o++){
                     for(int q=1;q<=m;q++){
                             System.out.print(cmr[o][q][0]+" ");
                     }
                System.out.println(" ");
               }
               int maxp=0;         //一个格子里最大点数
               for(int o=1;o<=r;o++){
                     for(int q=1;q<=m;q++){
                         if(cmr[o][q][0]>maxp)
                               
                       


System.out.println("m="+m);
System.out.println("r=="+r);
               System.out.println(" ");
                for (int o=1;o<=sqrtn;o++){
                     System.out.print(X[array[o]]+" ");
               }
               System.out.println(" ");
               for (int o=1;o<=sqrtn;o++){
                     System.out.print(Y[array[o]]+" ");
               }

                
  
 }


}