分治算法的应用

小灰灰 2023-05-30 10:47 1阅读 0赞

**题目描述：**  
——给出二维平面上的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坐标排序，分成左右两个部分，对 每个部分分别求最近点对的距离，然后进行合并。对于两个部分求得的最近距离d，合并过程应当检查宽为2d的带状区间是否有两个点分属于两个集合且距离小于d，最多可能有n个点，合并时间最坏情况下为O（n^2）。但是左边和右边中的点具有以下稀疏的性质，对于左边中的任意一点，右边中的点必定落在一个d\*2d的矩阵中，且最多只需检查6个点（鸽巢原理）。这样，先将带状区间的点按y坐标排序，然后线性扫描，这样合并的时间复杂度为O（nlogn），几乎为线性。

**参考代码：**

#include<cstdio>
    #include<iostream>
    #include<cmath>
    #include<algorithm>
    #include<iomanip>
    
    using namespace std;
    
    double MAX = 1e10;
    int a, b;
    
    struct Node
    {
    	double x, y;
    	int key;
    }
    ar[100005], br[100005];
    
    bool cmpx(Node a, Node b)
    {
    	return a.x < b.x;
    }
    
    bool cmpy(Node a, Node b)
    {
    	return a.y < b.y;
    }
    
    double min(double a, double b)
    {
    	return a < b ? a : b;
    }
    
    double dis(Node a, Node b)
    {
    	return sqrt(pow(a.x-b.x, 2) + pow(a.y-b.y, 2));
    }
    
    double cal(int s, int e)
    {
    	int mid, i, j, tail = 0;
    	double d;
    	if(s==e)	return MAX;
    	mid = (s + e) / 2;
    	d = min(cal(s, mid), cal(mid+1, e));
    	for(i=mid; i>=s && ar[mid].x - ar[i].x < d; i--)
    	{
    		br[tail++] = ar[i];
    	}
    	for(i=mid+1; i<e && ar[i].x - ar[mid].x < d; i++)
    	{
    		br[tail++] = ar[i];
    	}
    	sort(br, br+tail, cmpy);
    	for(i=0; i<tail; i++)
    	{
    		for(j=i+1; j<tail && br[j].y - br[i].y < d; j++)
    		{
    			if(d > dis(br[i], br[j]))
    			{
    				a = min(br[i].key, br[i].key);
    				b = br[i].key + br[j].key - a;
    				d = min(d, dis(br[i], br[j]));
    			}
    		}
    	}
    	return d;
    }
    
    int main(void)
    {
    	int n;
    	while(cin>>n && n)
    	{
    		for(int i=0; i<n; i++)
    		{
    			ar[i].key = i+1;
    			scanf("%lf%lf", &ar[i].x, &ar[i].y);
    		}
    		sort(ar, ar+n, cmpx);
    		double d = cal(0, n);
    		printf("%.2lf\n", d/2.0);
    	}
    	
    	return 0;
    }