最近點對算法

1、算法：

1) 總體的思路：

A、首先根據快排算法将數組按照x軸對數組a進行排序；

B、總體采用遞歸的表現形式，處理方法為conquerPair，當點的數目為1時傳回無窮大，為2時，直接傳回兩點的距離；

C、對start到mid範圍的點使用conquerPair方法得到l_min, 對mid+1到end範圍的點使用conquerPair方法得到r_min

D、取d_min=Min（l_min，r_min）;

E、在x[mid]-d_min到x[mid]+d_min進行操作findMidMin方法操作，找出橫跨left區和right區的最小點，與d_min比較大小，得到的最小值即為最小值；

2） findMidMin方法的處理：

A、周遊在x[mid]-d_min範圍的每一個點i；

B、對于每一個點i，計算它與點j的距離，j的限制條件是：x在x[mid]到x[mid]+d_min，y在y[i]+d_min到y[i]-d_min；

C、同時，滿足要求的個數k<6,這一點後面證明；

D、将計算結果與d_min比較，傳回小的一個即可；

3）為什麼在限定範圍中隻需要找小于6個點，具體檢視：

http://blog.csdn.net/tzh476/article/details/52669344

由下圖知，假設在圖中範圍存在6個點滿足小于d_min的點，分别位于不同的矩形中，在一個1/6的矩形中，最長為(5/6)*d_min,即一個矩形隻能有一個點，再增加一個點就會與d_min的大小産生沖突。

2、關鍵代碼：

1）代碼1，對應1中1）“總體的思路”：

private static double conquerPair(double[] x, double[] y, int start, int end) {
        int mid=(start+end)/,i=start,j=end;
        int num=end-start+;
        if(num==)
            return Integer.MAX_VALUE;
        else if(num==)
            return getDistance(x[i],y[i],x[j],y[j]);
        double l_min=conquerPair(x,y,start,mid);
        double r_min=conquerPair(x,y,mid+,end);
        double d_min=l_min<r_min?l_min:r_min;
        return findMidMin(x,y,mid,d_min,start,end);
    }
           

2）代碼2，對應1的2）中“findMidMin方法的處理”：

private static double findMidMin(double[] x, double[] y, int mid, double d_min,
            int start, int end) {
        double min=d_min,l_border=x[mid]-d_min,r_border=x[mid]+d_min,t_border,b_border,temp;
        int k;
        for(int i=mid;i>=start&&x[i]>l_border;i--){
            t_border=y[i]+d_min;
            b_border=y[i]-d_min;
            k=;//滿足要求的6個點的計數
            for(int j=mid+;j<=end&&k<&&x[j]<r_border;j++){
                if(y[j]<t_border&&y[j]>b_border){
                    k++;
                    temp=getDistance(x[i], y[i], x[j], y[j]);
                    if(min>temp)
                        min=temp;
                }
            }
        }
        return min;
    }