算法练手：“套圈”游戏（quoit）

原题还是英文的
在 Cyberground（赛博游乐场）中，每个玩具的位置是固定的，并且圆环被精心设计成“同一时刻只能圈住一个玩具”。同时，为了让游戏看起来更有趣，圆环被设计成尽可能大的半径。
现在给定场地中所有玩具的位置，你需要求出这样一个圆环的最大可能半径。
假设所有玩具都是平面上的点。如果一个点到圆心的距离 严格小于圆环半径，则该点被圈住。
如果有两个玩具在同一个位置，则该情况下圆环半径为 0。
输入
输入包含多组测试数据。
每组第一行是一个整数 N (2 ≤ N ≤ 100000)，表示玩具数量
接下来 N 行，每行包含一个点的坐标 (x, y)，表示一个玩具的位置
当 N = 0 时输入结束
输出
对每组数据输出一行，表示所需圆环的半径，结果保留 2 位小数。

这道题是**最近点对（Closest Pair of Points）**问题。圆环最大半径 = 最近两点距离 / 2。
算法思路：分治法，O(nlog²n)
按 x 坐标排序，递归分左右两半
合并时只考虑距分界线距离 < d 的点，按 y 排序后每点只需检查最多 7 个邻居

按照书本上的，我们可以照葫芦画瓢

#include<iostream>#include<algorithm>#include<cmath>#include<iomanip>usingnamespacestd;constintMAXN=100000+5;constdoubleINF=1e100;structPoint{doublex,y;}p[MAXN],tmp[MAXN];boolcmpx(Point a,Point b){if(a.x==b.x)returna.y<b.y;returna.x<b.x;}boolcmpy(Point a,Point b){returna.y<b.y;}doubledist(Point a,Point b){doubledx=a.x-b.x;doubledy=a.y-b.y;returnsqrt(dx*dx+dy*dy);}doubleclosest(intl,intr){// 只有一个点if(l>=r)returnINF;// 两个点if(r-l==1){if(p[l].y>p[r].y)swap(p[l],p[r]);returndist(p[l],p[r]);}intmid=(l+r)/2;doublemidx=p[mid].x;doubled1=closest(l,mid);doubled2=closest(mid+1,r);doubled=min(d1,d2);// merge，保持按 y 排序inti=l;intj=mid+1;intk=l;while(i<=mid&&j<=r){if(p[i].y<p[j].y)tmp[k++]=p[i++];elsetmp[k++]=p[j++];}while(i<=mid)tmp[k++]=p[i++];while(j<=r)tmp[k++]=p[j++];for(intt=l;t<=r;t++)p[t]=tmp[t];// stripintcnt=0;for(intt=l;t<=r;t++){if(fabs(p[t].x-midx)<d)tmp[cnt++]=p[t];}// 检查 strip 中的点for(inti=0;i<cnt;i++){// 最多只需检查后面7个点for(intj=i+1;j<cnt&&(tmp[j].y-tmp[i].y)<d;j++){d=min(d,dist(tmp[i],tmp[j]));}}returnd;}intmain(){intn;while(cin>>n&&n){for(inti=0;i<n;i++){cin>>p[i].x>>p[i].y;}sort(p,p+n,cmpx);doubleans=closest(0,n-1);cout<<fixed<<setprecision(2)<<ans/2.0<<endl;}return0;}