Quoit Design
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 58566 Accepted Submission(s): 15511
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.
平面最近点对，即平面中距离最近的两点
分治算法：
int SOLVE(int left,int right)//求解点集中区间[left,right]中的最近点对
{
double ans; //answer
0) 调用前的预处理:对所有点排序,以x为第一关键词y为第二关键字 , 从小到大;
1) 将所有点按x坐标分成左右两部分;
/* 分析当前集合[left,right]中的最近点对，有两种可能：
1. 当前集合中的最近点对，点对的两点同属于集合[left,mid]或同属于集合[mid,right]
则ans = min(集合1中所有点的最近距离, 集合2中所有点的最近距离)
2. 当前集合最近点对中的两点分属于不同集合：[left,mid]和[mid,right]
则需要对两个集合进行合并，找出是否存在p∈[left,mid],q∈[mid,right],使得distance(p,q)小于当前ans(即步骤1中求得的ans);
*/
2) Mid = (left+right)/2;
ans = min( SOLVE(left,mid), SOLVE(mid,right) );
即：递归求解左右两部分中的最近距离，并取最小值；
//此步骤实现上文分析中的第一种情况
/*
再次进行分析
我们将集合[left,right]用x = mid这条直线分割成两部分
则如果画出直线l1:x=mid-ans 和 l2:x=mid+ans，显然如果有p∈[left,mid], q∈[mid,right]且distance(p,q) < ans则p,q一定在直线l1和直线l2之间，否则distance(p,q)必定大于ans。
于是扫描出在l1和l2之间的点
*/
3) 建立缓存数组temp[];
for i = left TO right
{
如果 abs(Point[i].x - Point[mid].x) <= ans
则向temp中加入点Point[i];
}
/*
对于temp中的点，枚举求所有点中距离最近两点的距离，然后与ans比较即可。
枚举的时候不必两两枚举。观察下图中的点p
于是我们可以对temp以y为唯一关键字从小到大排序,进行枚举, 更新ans,然后在枚举时判断：一旦枚举到的点与p点y值之差大于ans，停止枚举。最后就能得到该区间的最近点对。
*/
4) sort(temp);
for i = 0 TO k-1
{
for j = i+1 TO k-1
如果 temp[j].y - temp[i].y >= ans break;
ans = min( ans, distance(temp[i], temp[j]) );
}
5) return ans;
}
算法的时间复杂度
由鸽巢原理，代码中第四步的枚举实际上最多只会枚举6个点，效率极高（一种蒟蒻的证明请看下方的评论）
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 200000+5; const int mod = 2009; const double eps=1e-8; const int INF=0x7fffffff; int n; struct point{ double x,y; point(double x=0,double y=0):x(x),y(y) {} bool operator < (const point& p) const { if(x!=p.x) return x<p.x; else return y<p.y; } }p[N],tmp[N]; bool cmpy(point a,point 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 closest_pair(int left,int right){ double d=INF; if(left==right)//如果此时区间查到了单点，直接返回最大值 return d; if(left+1==right) //如果左区间与右区间只差一，就直接返回他们的距离 return dis(p[left],p[right]); int mid=(left+right)>>1; //计算中点，位运算加速 double d1=closest_pair(left,mid); //分别计算出两个区间的值 double d2=closest_pair(mid,right); d=min(d1,d2); //取两个区间中的最小值 int k=0; //计算数量 for(int i=left;i<=right;i++){ if(fabs(p[mid].x-p[i].x)<=d){ //如果x轴的坐标相减满足<=d载入数组 tmp[k++]=p[i]; } } //按照y轴的值排序，默认按照升序 sort(tmp,tmp+k,cmpy); for(int i=0;i<k;i++) for(int j=i+1;j<k&&tmp[j].y-tmp[i].y<d;j++){ //在已经筛出的数中计算最小值 double d3=dis(tmp[i],tmp[j]); d=min(d,d3); //如果有最小值更新 } return d; //直接返回最小值 } int main() { while(scanf("%d",&n),n){ for(int i=0;i<n;i++){ double a,b; scanf("%lf%lf",&a,&b); p[i]=point(a,b); } sort(p,p+n); //化成有序数列 printf("%.2lf\n",closest_pair(0,n-1)/2); //求的是半径，若求直径不必/2 } return 0; }