原题链接：
解析：此题为最近对模板题，用分治法求最短对问题，可以在O（nlongn）时间内求出。
易错点：
- + - 等符号与位移运算符 << 或者 >> 优先级没搞清楚，自以为位移运算符比 + - 高
- 谁减去谁要写正确，因为都是排好序的，所以必然在后面的大于前面的
代码实例：
#include#include #include #include using namespace std;const int N = 100010;const int inf = 10e8;struct Point{ double x,y;}toy[N];int tmp[N];//用来存放以mid为中点d为半径的矩形范围内的点的下标 bool cmpx(Point a,Point b){ return a.x < b.x;}bool cmpy(int a,int b){//对存有结构体下标的数组进行排序，这样就可以不改变结构体的情况下使其有序 return toy[a].y < toy[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 l,int r){ if(l == r) return inf;//返回无穷大 if(l + 1 == r) return dis(toy[l],toy[r]);//仅有俩个点，故此区间最短距离为 int mid = l+(r-l)/2; double d = min(closest_pair(l,mid),closest_pair(mid+1,r)); int cnt = 0; for(int i = l;i <= r;i++) if(fabs(toy[i].x-toy[mid].x) <= d) tmp[cnt++] = i; sort(tmp,tmp+cnt,cmpy); for(int i = 0;i < cnt;i++) for(int j = i+1;j < cnt && toy[tmp[j]].y - toy[tmp[i]].y < d;j++){ double d2 = dis(toy[tmp[i]],toy[tmp[j]]); if(d2 < d){ d = d2; break; } } return d;}int main(){ int n; while(~scanf("%d",&n) && n){ for(int i = 0;i < n;i++) scanf("%lf%lf",&toy[i].x,&toy[i].y);//数据大，效率高 sort(toy,toy+n,cmpx); printf("%.2f\n",closest_pair(0,n-1)/2); } return 0;}