问题描述：

在二维平面内给定n个点，寻找这些点中举例最近的两个点;

思路：

我们发现如果要将全部的点两两比较，则最起码需要O(n^2),因此我们的思路是如果要求与某个点A距离最近的点，则需要缩小范围，不用每个点都比较；

我们需要使用分治法来求解；

首先我们需要定义一些变量：

Px：对于点按照x坐标排序；

Py：对于点按照y坐标排序；

Qx：对于左部分的点按照x坐标排序；

Qy：对于部分的点按照y坐标排序；

Rx：对于右部分的点按照x坐标排序；

Ry：对于右部分的点按照y坐标排序；

递归的出口就是如果只有三个点以内，则直接两两计算距离，并返回最小距离；

我们可以从上面清晰的看出：每次将问题分割成两个小问题，因此T(n) = 2*T(n/2)+f(n);

f(n)是问题分隔和组合的消耗;

分隔时需要计算Qx,Qy,Rx,Ry,因此花费O(n)

组合时已经计算出了Q和R区域的最小距离，d = min(d1,d2)我们需要计算一个点在Q，一个点在R的最小距离，我们需要做如下步骤：

(1)对于分隔Q和R的线，向左和向右拓宽d，落在这个区域中的点都有可能是最小距离的点对，记为S； O（n）

(2)我们对S按照y排序后为Sy，对于Sy中每个点只需要计算与他的x、y坐标相差 2*d之内的点（最多15个点）； O（n）

(3)计算出S区域的最小距离后与d比较，取较小者；
O（1）

因此f(n) = O(n)

T(n) = 2*T(n/2) + O(n)  ===>   T(n) = O(nlogn)

代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;


public class Test {
	
	public static void main(String[] args) {
		initializePoint();
		Point[]result = closest_pair(P);
		dist = distance(result);
		System.out.println("距离最近的两点为：");
		print(result);
		System.out.println("距离为："+dist);
	}
	private static double dist;
	private static Point[] P;
	private static Comparator<Point> ycompar = new Comparator<Point>() {  //根据y坐标比较的比较器
		@Override
		public int compare(Point o1, Point o2) {
			if(o1.y<o2.y){
				return -1;
			}
			else if(o1.y>o2.y){
				return 1;
			}
			return 0;
		}
	};
	private static Comparator<Point> xcompar = new Comparator<Point>() {  	//根据x坐标比较的比较器
		@Override
		public int compare(Point o1, Point o2) {
			if(o1.x<o2.x){
				return -1;
			}
			else if(o1.x>o2.x){
				return 1;
			}
			return 0;
		}
	};
	

	//初始化点数组
	/**
	 * (0,0)
	 * (5,8)
	 * (9,5)
	 * (10,20)
	 * (100,100)
	 */
	private static void initializePoint() {
		P = new Point[5];
		for(int i=0;i<P.length;i++){
			P[i] = new Point();
		}
		P[0].x = 10;
		P[0].y = 20;
		P[1].x = 0;
		P[1].y = 0;
		P[2].x = 100;
		P[2].y = 100;
		P[3].x = 5;
		P[3].y = 8;
		P[4].x = 9;
		P[4].y = 5;
	}

	//主函数
	public static Point[] closest_pair(Point[] points) {
		Point[] px = points.clone();
		Arrays.sort(px,xcompar);
		Point[] py = points.clone();
		Arrays.sort(py,ycompar);
		Point[] result = closest_pair_rec(px,py);
		return result;
		
	}
	
	public static Point[] closest_pair_rec(Point[]px,Point[]py){
		
		Point minFirstPoint = null;
		Point minSecondPoint = null;
		double mindistance = 0;
		
		if(px.length<=3){		//出口
			double mindist = Double.MAX_VALUE;
			int mini = 0;
			int minj = 0;
			for(int i=0;i<px.length;i++){
				for(int j=i+1;j<px.length;j++){
					if(mindist>distance(new Point[]{px[i],px[j]})){
						mindist = distance(new Point[]{px[i],px[j]});
						mini = i;
						minj = j;
					}
				}
			}
			return new Point[]{px[mini],px[minj]};
		}
		Point[] Q = Arrays.copyOfRange(px, 0, px.length/2+1);
		Point[] R = Arrays.copyOfRange(px, px.length/2+1, px.length);
		
		Point[] Qx = Q.clone();
		Arrays.sort(Qx, xcompar);
		Point[] Qy = Q.clone();
		Arrays.sort(Qy, ycompar);
		
		Point[] Rx = R.clone();
		Arrays.sort(Rx, xcompar);
		Point[]Ry = R.clone();
		Arrays.sort(Ry, ycompar);
		
		Point[] q = closest_pair_rec(Qx,Qy);
		Point[] r = closest_pair_rec(Rx,Ry);
		
		double qd = distance(q);
		double rd = distance(r);
		double delta = Math.min(qd,rd);
		if(delta==qd){
			minFirstPoint = q[0];
			minSecondPoint = q[1];
		}
		else{
			minFirstPoint = r[0];
			minSecondPoint = r[1];
		}
		mindistance = delta;
		
		int maxx = Qx[Qx.length-1].x;	//分割线
		
		//找到与分割线距离小于delta的部分点放到S中
		ArrayList<Point> Stmp = new ArrayList<Point>();
		for(int i=0;i<px.length;i++){
			if(Math.abs(px[i].x-maxx)<delta){
				Stmp.add(px[i]);
			}
		}
		Point[]S = Stmp.toArray(new Point[0]);
		Point[] Sy = S.clone();
		Arrays.sort(Sy,ycompar);
		
		//寻找15个点之内的点，并比较距离,找出最小距离的得点 ，每个点至多比较8个点，因此复杂度为O(8n)
		double secondMinDistance = Double.MAX_VALUE;
		Point tmpminFirst = null;
		Point tmpminSecond = null;
		for(int i=0;i<Sy.length;i++){
			Point basep = Sy[i];
			for(int j=i+1;j<Sy.length;j++){
				Point compp = Sy[j];
				if((compp.y-basep.y < 2*delta)&&Math.abs(compp.x-basep.x)<2*delta){	//如果在15个点之内，即x和y坐标相差都在2*delta之内	
					double tmpdis = distance(new Point[]{basep,compp});
					if(secondMinDistance>tmpdis){
						secondMinDistance = tmpdis;
						tmpminSecond = compp;
						tmpminFirst = basep;
					}
				}
				else{
					break;
				}
			}
		}
		if(secondMinDistance<mindistance){
			return new Point[]{tmpminFirst,tmpminSecond};
		}
		else{
			return new Point[]{minFirstPoint,minSecondPoint};
		}
	}
	
	private static double distance(Point[] q) {
		return Math.pow(Math.pow(q[0].x-q[1].x,2)+Math.pow(q[0].y-q[1].y,2), 0.5);
	}

	private static void print(Point[]ps){
		for(Point p:ps){
			System.out.println("x="+p.x+",y="+p.y);
		}
	}
}

class Point{
	int x;
	int y;
}