套圈（最近点对问题）

蔚落 2022-05-30 10:20 271阅读 0赞

Problem Description

Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.  
In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.  
  
Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

Input

The input consists of several test cases. For each case, the first line contains an integer N (2 <= N <= 100,000), the total number of toys in the field. Then N lines follow, each contains a pair of (x, y) which are the coordinates of a toy. The input is terminated by N = 0.

Output

For each test case, print in one line the radius of the ring required by the Cyberground manager, accurate up to 2 decimal places.

Sample Input

20 01 121 11 13-1.5 00 00 1.50

Sample Output

0.710.000.75

解法一：O（n^2）暴力枚举

先按x升序排序，如果x相等的话按y升序排序

然后来个二重循环每个点与其他的点计算一下距离。先将min1 min2都置为无限大（INF=0x3f3f3f3f）

每个点算完后的到一个min1，如果S(用距离公式计算的两点距离)大于min1，就可以break了，因为点是排好序的，再往下算还是会更大。得到一个min1再与min2比较一下。这样O（n^2）时间后就得到了答案min2。

![70][]

#include<cstdio>   
    #include<algorithm>   
    #include<cmath>   
    #define INF 0x3f3f3f3f   
    using namespace std;
    
    struct node
    {
    	double x;
    	double y;
    }a[100010];
    
    int cmp(node a, node b)
    {
    	if (a.x == b.x)
    		return a.y<b.y;
    	return a.x<b.x;
    }
    
    double del(node a, node b)
    {
    	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
    }
    
    int main()
    {
    	int n;
    	double min1, min2, s;
    	while (scanf("%d", &n) && n)
    	{
    		for (int i = 0; i<n; i++)
    			scanf("%lf %lf", &a[i].x, &a[i].y);
    		sort(a, a + n, cmp);
    		min2 = INF;
    		for (int i = 0; i<n - 1; i++)
    		{
    			min1 = INF;
    			for (int j = i + 1; j<n; j++)
    			{
    				s = del(a[i], a[j]);
    				if (s<min1)
    					min1 = s;
    				else
    					break;
    			}
    			if (min1<min2)
    				min2 = min1;
    		}
    		printf("%.2lf\n", min2 / 2.0);
    	}
    	return 0;
    }

解法二：分治（nlogn）

参考题解：[http://blog.csdn.net/Cxiaokai/article/details/6661005][http_blog.csdn.net_Cxiaokai_article_details_6661005]

很厉害的分治方法，学习。

先按照x坐标升序排序，这样得到一组x下标有序的序列。根据序列大小找到中间元素的下标mid，这样把这组序列划分成两组，分别找到这两组的点对中的最小值。用Ans记录两组中的最小值。然后递归下去，把一个组再划分为两个组，按照上面说的找。以下标为mid的元素作为基准，在L到R的区间里找x坐标与基准元素x坐标差小于等于Ans的放入tmp数组中，然后将tmp数组按照y坐标升序排序，在这些点中找最小的距离，然后更新最小距离。

![70 1][]

#include<math.h>  
    #include<stdio.h>  
    #include<iostream>  
    #include<algorithm>  
    using namespace std;
    
    typedef struct node Point;
    
    struct node
    {
    	double x;
    	double y;
    }p[100010];
    
    Point tmp[100010];
    
    
    int compx(node a, node b)
    {
    	return a.x < b.x;
    }
    
    int compy(node a, node b)
    {
    	return a.y < b.y;
    }
    
    double  dis(Point a, Point b)
    {
    	return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
    }
    
    double ans(int l, int r)
    {
    	//if (l == r) return 0;
    	if (l + 1 == r)return dis(p[l], p[r]);
    	if (l + 2 == r) return min(dis(p[l], p[l + 1]), min(dis(p[l], p[r]), dis(p[l + 1], p[r])));
    
    	int mid = (l + r) >>1;
    
    	double left = ans(l, mid); double right = ans(mid + 1, r);
    	double Ans = min(left, right);
    
    	int k = 0;
    	for (int i = l; i <= r;i++)
    	if (fabs(p[i].x-p[mid].x)<=Ans)
    		tmp[k++] = p[i];
    
    	sort(tmp, tmp + k, compy);
    
    	for (int i = 0; i < k;i++)
    	for (int j = i + 1; j < k; j++)
    	{
    
    		if (tmp[j].y - tmp[i].y >= Ans) break;
    			Ans = min(Ans, dis(tmp[i], tmp[j]));
    	}
    
    	return Ans;
    }
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int n;
    
    	while (scanf("%d", &n)&&n)
    	{
    		for (int i = 0; i < n; i++)
    			scanf("%lf %lf", &p[i].x, &p[i].y);
    
    		sort(p,p+n,compx);
    		printf("%.2f\n", ans(0,n-1)/2);
    	}
    
    
    	return 0;
    }

很费解，用了正规的分治方法时间竟然比O（n^2）的慢，是因为数据的原因吗？哈哈哈哈哈哈！

[70]: /images/20220530/fefb230e91c84f6882b531f1afab0303.png
[http_blog.csdn.net_Cxiaokai_article_details_6661005]: http://blog.csdn.net/Cxiaokai/article/details/6661005
[70 1]: /images/20220530/ee92c220f9634cecbb805392a2377b08.png