程式設計之美-最近點對

最近又翻出了上個學期寫的java作業，重溫了一下分治，那時候看這道題還是有些地方不是很明白，現在回頭看了一遍重新梳理了一下思路并把之前沒寫好的注釋重寫了一遍。

關于最近點對的問題已經有很多人分析過了，其實關鍵還是把問題細分成各個子問題然後再由子問題答案歸結出最終答案。這道題關鍵就在把點集劃分成左右兩個子集，分别求解，再合并，最近點對要不出現在左集合，要不出現在右集合，要不就兩點跨越左右集合，遞歸求解即可。

程式設計之美最後說到對分界處以兩邊最近點對距離為寬的帶狀區域内的點進行排序時，可以使用歸并排序，并與計算最近點對結合一起做，暫時還未實作。

package com.java.homework;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.Iterator;
import java.util.Scanner;

import com.sun.xml.internal.stream.Entity.ScannedEntity;

public class CloseDots{
    //點結構
    private class Point{
        public Point(){
            x = ;
            y = ;
        }
        double x;
        double y;
    }
    //點對結構
    private class DoubleP{
        Point a = new Point();
        Point b = new Point();
        double length = Double.MAX_VALUE;
    }
    //點集
    private ArrayList<Point> m_arr;

    public static void main(String[] args){
        CloseDots cd = new CloseDots();
        cd.m_arr = new ArrayList<Point>();
        cd.inputPoint();
        cd.sortList();
        cd.printPoint();
        DoubleP close = cd.closePart(, cd.getPointNum()-);
        System.out.println("點1：" + "("+close.a.x + ","+close.a.y + ")");
        System.out.println("點2：" + "("+close.b.x + ","+close.b.y + ")");
        System.out.println("最近距離："+ close.length);
    }
    //輸入點
    private void inputPoint(){
        Scanner s = new Scanner(System.in);
        System.out.println("點的個數：");
        int n = s.nextInt();
        while(n <= ){
            System.out.println("輸入無效");
            System.out.println("點的個數：");
            n = s.nextInt();
        }
        int len = n;
        while(n-- != ){
            Point p = new Point();
            try{
                System.out.println("第"+(len-n)+"個點：");
                p.x = s.nextDouble();
                p.y = s.nextDouble();
                m_arr.add(p);
            }catch(InputMismatchException e){
                System.out.println("非法輸入");
                //彈出非法字元
                s.next();
                //重置這次輸入
                n++;
            }
        }
        s.close();
        System.out.println("輸入結束");
    }
    //點排序
    private void sortList(){
        Collections.sort(m_arr,new Comparator<Point>() {
            public int compare(Point arg1,Point arg2){
                return (int)cmp(arg1,arg2);
            }
        });
    }
    //列印點
    private void printPoint(){
        Iterator<Point> it = m_arr.iterator();
        while(it.hasNext()){
            Point p = it.next();
            System.out.println("x:"+p.x+" y:"+p.y);
        }
    }
    //擷取點集長度
    private int getPointNum(){
        return m_arr.size();
    }

    private DoubleP minAB(DoubleP a,DoubleP b){
        return a.length>b.length?b:a;
    }
    private double dis(Point a,Point b){
        return Math.sqrt((a.x-b.x)*(a.x-b.x) + 
                            (a.y-b.y)*(a.y-b.y));
    }
    private double cmp(Point a,Point b){
        if(a.x != b.x)
            return a.x -b.x;
        return a.y -b.y;
    }
    //遞歸計算最近點對
    private DoubleP closePart(int left,int right){
        DoubleP dp = new DoubleP();
        //隻有一個點，傳回Double.MAX_VALUE長度
        if(left == right)
            return dp;
        //相鄰兩點，傳回兩點距離
        if(left+ == right){
            dp.a = m_arr.get(left);
            dp.b = m_arr.get(right);
            dp.length = dis(m_arr.get(left),m_arr.get(right));
            return dp;
        }
        //分割子問題
        int min = (left+right)/;
        DoubleP dp1 = closePart(left, min);
        DoubleP dp2 = closePart(min+,right);
        //擷取兩個子問題中最小點對
        dp = minAB(dp1, dp2);
        //計算跨越分界的點對
        //找出位于分界兩邊距離中心點水準距離小于兩邊最小點對的點集（隻有這些點可能成為最近點對）
        ArrayList<Integer> temp = new ArrayList<Integer>();
        for(int i = left;i<right;++i){
            if(Math.abs(m_arr.get(min).x - m_arr.get(i).x)<dp.length){
                temp.add(i);
            }
        }
        //區域内的點按Y排序
        Collections.sort(temp,new Comparator<Integer>() {
            public int compare(Integer arg1,Integer arg2){
                return (int)(m_arr.get(arg1).y - m_arr.get(arg2).y);
            }
        });
        //由以上條件可知對于隻有落于dp.length*(2*dp.length)矩形區域内的點才可能成為更小的點對
        //并且在這個區域内最多可存在8個點（分别位于矩形區域兩個相鄰邊長為dp.length的正方形的四角）
        //是以隻需順序掃一遍臨時數組，然後考察緊跟每個點的後7個點即可，可以在O(N)的時間内完成
        for(int i = ; i<temp.size();++i){
            for(int j = i+;j<i+ && j<temp.size() && 
                    (m_arr.get(temp.get(j)).y - m_arr.get(temp.get(i)).y)<dp.length;
                    ++j){
                DoubleP dp3 = new DoubleP(); 
                dp3.a = m_arr.get(temp.get(i));
                dp3.b = m_arr.get(temp.get(j));
                dp3.length = dis(m_arr.get(temp.get(i)),m_arr.get(temp.get(j)));
                if(dp3.length<dp.length)
                    dp = dp3;
            }
        }
        return dp;
    }
}