编程之美-最近点对

最近又翻出了上个学期写的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;
    }
}