//Closest Pair Points

import java.text.NumberFormat;

public class ClosestPairPoint
{
	static final int SIZE=40;

	public static void main(String[] args)
	{
		DPoint[] points=new DPoint[SIZE];

		for(int i=0;i<SIZE;i++)
		{
			int x=(int)(Math.random()*1000);
			int y=(int)(Math.random()*1000);
			points[i]=new DPoint(x,y);
		}

		java.util.Arrays.sort(points);

		for(int i=0;i<points.length;i++)
			System.out.println(points[i]);

		DPoint[] result=new DPoint[2];
		result=closestPoint(points);

		NumberFormat format=NumberFormat.getNumberInstance();
		format.setMaximumFractionDigits(3);

		double distant=Math.sqrt(Math.pow((result[0].x-result[1].x),2)+
								  Math.pow((result[0].y-result[1].y),2));
		System.out.println("The result of Point is: "+result[0]+" "+result[1]);
		System.out.println("The distant of closest pair point is: "+
				format.format(distant));
	}

	public static DPoint[] closestPoint(DPoint[] points)
	{
		//The result Array
		DPoint[] item=new DPoint[2];

		//If the size is small,then directly return the closest point
		if(points.length<=3)
		{
			double distant=Double.MAX_VALUE;
			int i;
			for(i=0;i<points.length;i++)
				for(int j=i+1;j<points.length;j++)
				{
					double dist=Math.sqrt(Math.pow((points[i].x-points[j].x),2)+
									  Math.pow((points[i].y-points[j].y),2));
					if(distant>dist)
					{
						distant=dist;
						item[0]=points[i];
						item[1]=points[j];
					}
				}
			return item;
		}

		//The LeftHalf Array
		DPoint[] pair1=new DPoint[2];
		//The rightHalf Array
		DPoint[] pair2=new DPoint[2];

		int len=(int)points.length/2;
		DPoint[] pointsLeft=new DPoint[len];
		DPoint[] pointsRight=new DPoint[points.length-len];

		for(int i=0;i<len;i++)
			pointsLeft[i]=points[i];
		for(int i=0;i<points.length-len;i++)
			pointsRight[i]=points[i+len];

		//The leftHalf Array's closest point
		pair1=closestPoint(pointsLeft);

		//The rightHalf Array's closest point
		pair2=closestPoint(pointsRight);

		double distant1=Math.sqrt(Math.pow((pair1[0].x-pair1[1].x),2)+
								  Math.pow((pair1[0].y-pair1[1].y),2));
		double distant2=Math.sqrt(Math.pow((pair2[0].x-pair2[1].x),2)+
								  Math.pow((pair2[0].y-pair2[1].y),2));

		double distant;

		if(distant1>distant2)
		{
			item=pair2;
			distant=distant2;
		}
		else
		{
			item=pair1;
			distant=distant1;
		}

		//Between left and right half,find the closest point
		int midCoordinate=points[len].x;

		int xDown=(int)midCoordinate-(int)distant;
		int xUpper=(int)midCoordinate+(int)distant;

		int count=0;
		for(int i=0;i<points.length;i++)
		{
			if(points[i].x>xDown&&points[i].x<xUpper)
				count++;
		}

		DPoint[] midPoint=new DPoint[count];

		int index=0;
		for(int i=0;i<points.length;i++)
		{
			if(points[i].x>xDown&&points[i].x<xUpper)
				midPoint[index++]=points[i];
		}

		int i;
		for(i=0;i<midPoint.length;i++)
			for(int j=i+1;j<midPoint.length;j++)
			{
				double dist=Math.sqrt(Math.pow((midPoint[i].x-midPoint[j].x),2)+
								  Math.pow((midPoint[i].y-midPoint[j].y),2));
				if(dist<distant)
				{
					distant=dist;
					item[0]=midPoint[i];
					item[1]=midPoint[j];
				}
			}
		return item;
	}
}