1.暴力
//按x第一关键词，按y第二关键词排，这样当if(a[j].x - a[i].x >= ans)时，后面的j一定不会比已有ans更优秀，疯狂剪枝。 #include<bits/stdc++.h> using namespace std; int n; const int maxn = 100010; double ans = 0x7fffffff; struct node{ int x, y; } a[maxn]; bool cmp(node p, node q){ if(p.x == q.x) return p.y < q.y; return p.x < q.x; } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i].x >> a[i].y; /*maxx = max(a[i].x, maxx); maxy = max(a[i].y, maxy);*/ } sort(a+1, a+n+1, cmp); for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++){ if(a[j].x - a[i].x >= ans) break; double now = sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2)); ans = min(now, ans); } printf("%.3lf\n", ans); return 0; }2.分治
//切记sqrt()中要加(double)!!!!! //3 1113333 223332 33333333 333333 23 23 #include<bits/stdc++.h> using namespace std; int n; const int maxn = 100010; const int inf = 0x3f3f3f3f; struct node{ int x, y; } a[maxn], t[maxn]; bool cmp(node p, node q){ if(p.x != q.x) return p.x < q.x; return p.y < q.y; } bool cmpy(node p, node q){ return p.y < q.y; } double dis(node p, node q){ return sqrt((double)(p.x - q.x)*(p.x - q.x) + (double)(p.y - q.y)*(p.y - q.y)); } double changsort(int x, int y){ double ans = 0x3fffffff; if(y - x == 1) return inf; if(y - x == 2) return dis(a[x], a[x+1]); int m = x + (y-x)/2; double d1 = changsort(x, m); double d2 = changsort(m, y); ans = min(d1, d2); int cnt = 0; for(int i = x; i <= m; i++) if(fabs(a[i].x - a[m].x) < ans){ t[++cnt].x = a[i].x; t[cnt].y = a[i].y; } sort(t+1, t+cnt+1, cmpy); for(int i = 1; i <= cnt; i++) for(int j = i+1; j <= cnt && abs(t[i].y - t[j].y) < ans; j++){ double d3 = dis(t[i], t[j]); ans = min(ans, d3); } return ans; } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i].x >> a[i].y; /*maxx = max(a[i].x, maxx); maxy = max(a[i].y, maxy);*/ } sort(a+1, a+n+1, cmp); printf("%.3lf\n", changsort(1, n+1)); return 0; }