pointnear.java

分治法解决最近点对问题

import java.io.IOException;
import java.math.*;
import java.util.Calendar;
import java.util.*;
import java.text.*; 


class Point{  
    int x;  
    int y;  
};



public class pointNear {

	double INF=1e20;
 
	
	public void showTime(){
		Calendar c = Calendar.getInstance();
		//Calendar c = new GregorianCalendar(); 
		int hour = c.get(Calendar.HOUR_OF_DAY); 
		int minute = c.get(Calendar.MINUTE); 
		int second = c.get(Calendar.SECOND);  
		/*
		Date now = new Date();
		hour=now.getHours(); 
		minute=now.getMinutes(); 
		second=now.getSeconds(); 

	    DateFormat d = DateFormat.getDateInstance(); 
	    String str = d.format(now);
	    return str;
	    */
	    System.out.println("Time is: "+hour+":"+minute+":"+second); 
		//Date now=new Date(); 
		//year=now.getYear(); 
		//month=now.getMonth()+1; 
		//day=now.getDate(); 
		//hour=now.getHours();
		//minute=now.getMinutes();
		//second=now.getSeconds();

	}
	public double dist(Point a,Point b){  
		return Math.sqrt((float)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));  
	}
	public double nearest1(Point[] points,int l,int r){
  
       int n=r-l;
       if(n==2)
       {
       		double d1=dist(points[l],points[l+1]);
       		double d2=dist(points[l+1],points[r]);
       		double d3=dist(points[l],points[r]);
       		if(d1<=d2&&d1<=d3)
       		{
       			return d1;
       		}
         
       		else if(d2<=d3)
       		{
       			return d2;
       		}
       		else
       		{
       			return d3;
       		}
        
       }
       if(n==1)
       {
       		double b=dist(points[l],points[r]);  
       		return b;
       }
       if(n==0)
       {
       		return INF;
       }
       
       int m=points[n/2+l].x;
       double left=nearest1(points,l,l+n/2);  
       double right=nearest1(points,l+n/2,r);  
       double temp_nearest=left<right?left:right;  
       
       double ret=temp_nearest; 
       for(int i=n/2-1+l;i>=0&&points[i].x>m-temp_nearest;i--)
       {  
           for(int j=n/2+l;j<=r&&points[j].x<m+temp_nearest;j++)
           {  
           		double t=dist(points[i],points[j]); 
           		if(t<ret)
           		{  
           			ret=t;   
           		}  
           }  
       } 
       return ret;  
   } 
	
	
	public  double nearest3(Point[] points,int l,int r){
	  	   int count;
	       int n=r-l;
	       if(n==2)
	       {
	       		double d1=dist(points[l],points[l+1]);
	       		double d2=dist(points[l+1],points[r]);
	       		double d3=dist(points[l],points[r]);
	       		if(d1<=d2&&d1<=d3)
	       			return d1;
	       		else if(d2<=d3)
	       			return d2;
	       		else
	       			return d3;  
	       }
	       
	       if(n==1)
	       {
	       		double onedis=dist(points[l],points[r]);  
	       		return onedis;
	       }
	       if(n==0)
	       		return INF;
	       sortX(points,points.length);
	       int m=points[n/2+l].x;
	       double left=nearest3(points,l,l+n/2);  
	       double right=nearest3(points,l+n/2+1,r);  
	       double temp_nearest=left<right?left:right;  
	       
	       double ret=temp_nearest; 
	       for(int i=n/2-1+l;i>=0&&points[i].x>m-temp_nearest&&points[i].x<m;i--)
	       {
	       		count=exist3(points,points[i],ret);
	       		Point[]temp=new Point[count];
	       		for(int s=0;s<count;s++)
	       		{
	       			temp[s]=new Point();
	       		}
	       		compare3(points,points[i],ret,temp);
	       	   
	       	   //for(int k=0;k<count;k++)
       	   			//temp[k]=new Point();	
	       	  // compare3(points,points[i],ret,temp,count);
	           for(int j=0;j<temp.length;j++)
	           {  
	           		double t=dist(points[i],temp[j]); 
	           		if(t<ret)
	           		{  
	           			ret=t;   
	           		}  
	           }  
	       } 
	       return ret;  
	   } 
	
	public  double nearest4(Point[] points,int l,int r){
		  	   int count;
		       int n=r-l;
		       if(n==2)
		       {
		       		double d1=dist(points[l],points[l+1]);
		       		double d2=dist(points[l+1],points[r]);
		       		double d3=dist(points[l],points[r]);
		       		if(d1<=d2&&d1<=d3)
		       			return d1;
		       		else if(d2<=d3)
		       			return d2;
		       		else
		       			return d3;  
		       }
		       
		       if(n==1)
		       {
		       		double onedis=dist(points[l],points[r]);  
		       		return onedis;
		       }
		       if(n==0)
		       		return INF;
		       sortX(points,points.length);
		       int m=points[n/2+l].x;
		       double left=nearest4(points,l,l+n/2);  
		       double right=nearest4(points,l+n/2+1,r);  
		       double temp_nearest=left<right?left:right;  
		       
		       double ret=temp_nearest; 
		       for(int i=n/2-1+l;i>=0&&points[i].x>m-temp_nearest&&points[i].x<m;i--)
		       {
		       	   count=exist4(points,points[i],ret);
		       	   Point[]temp=new Point[count];
		       	   for(int k=0;k<count;k++)
		       	   		temp[k]=new Point();
		       	   compare4(points,points[i],ret,temp);
		           for(int j=0;j<temp.length&&count!=0;j++)
		           {  
		           		double t=dist(points[i],temp[j]); 
		           		if(t<ret)
		           		{  
		           			ret=t;   
		           		}  
		           }  
		       } 
		       return ret;  
		   } 
	
   public  void sortX(Point[] P,int n){                //排序 
    
   		Point temp = new Point();
   		for(int i=0;i<n-1;i++)
   			for(int j=i+1;j<n;j++)
   			{
   				if(P[i].x > P[j].x)
   				{
   					temp.x=P[i].x;
   					temp.y=P[i].y;
   					P[i].x=P[j].x;
   					P[i].y=P[j].y;
   					P[j].x=temp.x;
   					P[j].y=temp.y;
   				}
   			}
   }
   
   public  void sortY(Point[] P,int n){                //排序 
    
   		Point temp = new Point();
   		for(int i=0;i<n-1;i++)
   			for(int j=i+1;j<n;j++)
   			{
   				if(P[i].y > P[j].y)
   				{
   					temp.x=P[i].x;
   					temp.y=P[i].y;
   					P[i].x=P[j].x;
   					P[i].y=P[j].y;
   					P[j].x=temp.x;
   					P[j].y=temp.y;
   				}
   			}
   }
 
   
   public int exist3(Point[]P,Point p1,double wight){
		int count=0;
		int rem1=0;
		int rem2=0;
		for(int j=0;j<P.length;j++)
		{
			if(P[j].x==p1.x)
				rem1=j;
				
			if(P[j].x>=p1.x+wight)
			{
				rem2=j;
				break;
			}
		}
		for(int i=rem1+1;i<rem2;i++)
		{
			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<Math.sqrt((float)(wight*wight-P[i].x*P[i].x))&&P[i].y>-Math.sqrt((float)(wight*wight-P[i].x*P[i].x)))
				count++;
		}
		return count;		
}
   
   public void compare3(Point[]P,Point p1,double wight,Point[]temp){
		int count=0;
		//int m;
		int rem1=0;
		int rem2=0;
		for(int j=0;j<P.length;j++)
		{
			if(P[j].x==p1.x)
				rem1=j;
			if(P[j].x>=p1.x+wight)
			{
				rem2=j;
				break;
			}
		}
		for(int i=rem1+1;i<rem2;i++)
		{
			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<Math.sqrt((float)(wight*wight-P[i].x*P[i].x))&&P[i].y>-Math.sqrt((float)(wight*wight-P[i].x*P[i].x)))
				count++;
		}
	//	for(int m=0;m<count;m++)
		//{
			//temp[m]=new Point();
		//}
		for(int i=rem1+1,m=0;i<rem2&&m<count;i++)
		{
			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<Math.sqrt((float)(wight*wight-P[i].x*P[i].x))&&P[i].y>-Math.sqrt((float)(wight*wight-P[i].x*P[i].x)))
			{
				temp[m].x=P[i].x;
				temp[m].y=P[i].y;
				m++;
			}
		}
}
   
   public void compare4(Point[]P,Point p1,double wight,Point[]temp){
	int count=0;
	//int m;
	int rem1=0;
	int rem2=0;
	for(int j=0;j<P.length;j++)
	{
		if(P[j].x==p1.x)
			rem1=j;
		if(P[j].x>=p1.x+wight)
		{
			rem2=j;
			break;
		}
	}
	for(int i=rem1+1;i<rem2;i++)
	{
		if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
			count++;
	}
//	for(int m=0;m<count;m++)
	//{
		//temp[m]=new Point();
	//}
	for(int i=rem1+1,m=0;i<rem2&&m<count;i++)
	{
		if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
		{
			temp[m].x=P[i].x;
			temp[m].y=P[i].y;
			m++;
		}
	}
}
   
   public void countNum4(Point[]P,Point p1,double wight,Point[]temp){
	int count=0;
	int tempy=p1.y;
	int remx1=0;
	int remx2=0;
	int remy1=0;
	int remy2=0;
	int remy3=0;
	
	for(int j=0;j<P.length;j++)
	{
		if(P[j].x==p1.x)
			remx1=j;
		if(P[j].x>=p1.x+wight)
		{
			remx2=j;
			break;
		}
		if(P[j].y==p1.y)
			remy1=j;
	}
	for(int i=remx1+1;i<remx2;i++)
	{
		if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
			count++;
	}
//	for(int m=0;m<count;m++)
	//{
		//temp[m]=new Point();
	//}
	for(int i=remx1+1,m=0;i<remx2&&m<count;i++)
	{
		if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
		{
			temp[m].x=P[i].x;
			temp[m].y=P[i].y;
			m++;
		}
	}
}
   
   public int exist4(Point[]P,Point p1,double wight){
   		int count=0;
   		int rem1=0;
		int rem2=0;
		for(int j=0;j<P.length;j++)
		{
			if(P[j].x==p1.x)
				rem1=j;
			if(P[j].x>=p1.x+wight)
			{
				rem2=j;
				break;
			}
		}
   		for(int i=rem1+1;i<rem2;i++)
   		{
   			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
   				count++;
   		}
   		return count;		
   }
 
   /*
   public void compare3(Point[] P,Point p1,double wight,Point[]temp,int count){

		//sortY(P,P.length);

		if(count==3)
		{
			//temp=new Point[3];
			for(int i=0,j=0;i<P.length&&j<count;i++)
	   		{
				if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<Math.sqrt((float)(wight*wight-P[i].x*P[i].x))&&P[i].y>-Math.sqrt((float)(wight*wight-P[i].x*P[i].x)))
	   			{
	   				temp[j].x=P[i].x;
	   				temp[j].y=P[i].y;
	   				j++;
	   			}
	   			
	   		}
		}
			///*
		if(count==2)
		{
			for(int i=0,j=0;i<P.length&&j<2;i++)
	   		{
				if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<Math.sqrt((float)(wight*wight-P[i].x*P[i].x))&&P[i].y>-Math.sqrt((float)(wight*wight-P[i].x*P[i].x)))
	   			{
	   				temp[j].x=P[i].x;
	   				temp[j].y=P[i].y;
	   				j++;
	   			}
	   			
	   		}
		}
		if(count==1)
		{
			for(int i=0,j=0;i<P.length&&j<1;i++)
	   		{
				if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<Math.sqrt((float)(wight*wight-P[i].x*P[i].x))&&P[i].y>-Math.sqrt((float)(wight*wight-P[i].x*P[i].x)))
	   			{
	   				temp[j].x=P[i].x;
	   				temp[j].y=P[i].y;
	   				j++;
	   			}
	   			
	   		}
		}
		//
}
*/  
 /*  
   public void compare4(Point[] P,Point p1,double wight,Point[]temp,int count){
   		//int y;
   		//Point[]temp;
   		//int count;
   		int locate;
   		//int j;
   		//sortY(P,P.length);
   		//count=exist(P,p1,wight);
   		//temp=new Point[count];
   		if(count==4)
   		{
   			//temp=new Point[4];
   			for(int i=0,j=0;i<P.length&&j<count;i++)
   	   		{
   	   			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
   	   			{
   	   				temp[j].x=P[i].x;
   	   				temp[j].y=P[i].y;
   	   				j++;
   	   			}
   	   			
   	   		}
   		}
   			
   		if(count==3)
   		{
   			//temp=new Point[3];
   			for(int i=0,j=0;i<P.length&&j<3;i++)
   	   		{
   	   			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
   	   			{
   	   				temp[j].x=P[i].x;
   	   				temp[j].y=P[i].y;
   	   				j++;
   	   			}
   	   			
   	   		}
   		}
   		if(count==2)
   		{
   			//temp=new Point[2];
   			for(int i=0,j=0;i<P.length&&j<2;i++)
   	   		{
   	   			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
   	   			{
   	   				temp[j].x=P[i].x;
   	   				temp[j].y=P[i].y;
   	   				j++;
   	   			}
   	   			
   	   		}
   		}
   		if(count==1)
   		{
   			//temp=new Point[1];
   			for(int i=0,j=0;i<P.length&&j<1;i++)
   	   		{
   	   			if(P[i].x<p1.x+wight&&P[i].x>p1.x&&P[i].y<p1.y+wight&&P[i].y>p1.y-wight)
   	   			{
   	   				temp[j].x=P[i].x;
   	   				temp[j].y=P[i].y;
   	   				j++;
   	   			}
   	   			
   	   		}
   		}
   		//
   		//return temp;
   }
   */
   public static void main(String[] args) { 
   		int num=1000;
   		Calendar CD = Calendar.getInstance();
   		/*
   		try{
   			num=System.in.read();
   		}catch (IOException e){
   			e.printStackTrace();
   		}
   		*/
   		pointNear pointnear=new pointNear();
   		Point[] P=new Point[num];
   		
   		for(int i=0;i<num;i++)
   		{
   			P[i]=new Point();
   			P[i].x=(int)(Math.random()*5000);
   			P[i].y=(int)(Math.random()*8000);
   		}
   		
   		System.out.println("随机生成的点的坐标如下:");
   		for(int i=0;i<num;i++)
   		{
   			System.out.println("("+P[i].x+","+P[i].y+")");
   		}
  
   		double min =pointnear.INF;
   		double min3 =pointnear.INF;
   		double min4 =pointnear.INF;
   		Point minP1 = new Point();
   		Point minP2 = new Point();
   		
   		System.out.println("Before algram1: "); 
   		pointnear.showTime();
   			
   		for(int i=0;i<num;i++)
   			for(int j=i+1;j<num;j++)
   			{
   				double d =pointnear.dist(P[i],P[j]);
   				if(d < min)
   				{
   					min=d;
   					minP1=P[i];
   					minP2=P[j];
   				}
   			}	
 
   		System.out.println("用蛮力算法得到的最近距离为:"+min);
   		System.out.println("最近点坐标为：("+minP1.x+","+minP1.y+")和("+minP2.x+","+minP2.y+")");
   		//System.out.println("蛮力算法消耗的时间为:"+left1);
   		
   		System.out.println("After algram1: "); 
   		pointnear.showTime();
   		
   		
   		pointnear.sortX(P,num);
  
   		System.out.println("按照横坐标排序后，各点坐标如下：");
   		for(int i=0;i<num;i++)
   		{
   			System.out.println("("+P[i].x+","+P[i].y+")");
   		}
   		
   		System.out.println("Before algram4: ");
   		pointnear.showTime(); 
   		
   		min4=pointnear.nearest4(P,0,num-1);

   		System.out.println("用分治算法(考虑4个点时)得到的最近距离为:"+min4);
   		//System.out.println("分治算法(考虑4个点时)消耗的时间为:"+left4);
   		
   		System.out.println("After algram4: "); 
   		pointnear.showTime();
   		
   		
   		System.out.println();
   		
   		System.out.println("Before algram3: "); 
   		pointnear.showTime();
   		
   		
   		min3=pointnear.nearest3(P,0,num-1);
   		System.out.println("用分治算法(考虑3个点时)得到的最近距离为:"+min3);
   		//System.out.println("分治算法(考虑3个点时)消耗的时间为:"+left3);
   		
   		System.out.println("After algram3: "); 
   		pointnear.showTime();
   		
   }
}