题目描述

　　给出二维平面上的n个点，求其中最近的两个点的距离的一半。

　　输入包含多组数据，每组数据第一行为n，表示点的个数；接下来n行，每行一个点的坐标。当n为0时表示输入结束，每组数据输出一行，为最近的两个点的距离的一半。

　　输入样例：

　　　　2

　　　　0 0

　　　　1 1

　　　　2

　　　　1 1

　　　　1 1

　　　　3

　　　　-1.5 0

　　　　0 0

　　　　0 1.5

　　　　0

　　输出样例：

　　　　0.71

　　　　0.00

　　　　0.75

题目解析：

　　采用分治的思想，把n个点按照x坐标进行排序，以坐标mid为界限分成左右两个部分，对左右两个部分分别求最近点对的距离，然后进行合并。对于两个部分求得的最近距离d，合并过程中应当检查宽为2d的带状区间是否有两个点分属于两个集合而且距离小于d，最多可能有n个点，合并时间最坏情况下是O(n^2).但是，左边和右边中的点具有以下稀疏的性质，对于左边中的任意一点，右边的点必定落在一个d*2d的矩形中，且最多只需检查6个点（鸽巢原理），这样，先将带状区间的点按照y坐标进行排序，然后线性扫描，这样合并的时间复杂度为O（nlogn）。

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;double MAX=1e10; //定义的最大距离，以在只有一个点的时返回无穷大int a,b;   //用来记录下标，与题无关struct Node{    double x,y;    int key;   //关键码，可有可无，与ab有关};Node ar[100005],br[100005];bool cmpx(Node a,Node b){return a.x
        
         =s&&ar[mid].x-ar[i].x
         
          dis(br[i],br[j])){ //更新点的值 //a=min(br[i].key,br[j].key); //b=br[i].key+br[j].key-a; d=min(d,dis(br[i],br[j])); } } } return d; //返回最小的点对之间的距离}int main(){ int n; while(cin>>n&&n){ for(int i=0;i