解题思路：分治法求平面最近点对。
将所有点排序后，，最近点对的距离就是下面两者的最小值：
（1） 两点p, q 同属于左半边或右半边时点对（p, q ) 的距离；
（2） 两点p, q属于不同区域时，距离小于d的点对（p, q）的距离。
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <vector>#include <algorithm>#define LL long longusing namespace std;const int INF = 0x3f3f3f3f;const int MAXN = 10000 + 10;const double eps = 1e-6;int N;typedef pair<double, double> Point;Point A[MAXN];bool compare_y(Point a, Point b){return a.second < b.second;}double closest_pair(Point *a, int n){if(n <= 1) return INF;int m = n / 2;double x = a[m].first;double d = min(closest_pair(a, m), closest_pair(a + m, n – m));inplace_merge(a, a + m, a + n, compare_y);vector<Point> b;for(int i=0;i<n;i++){if(fabs(a[i].first – x) >= d)continue;for(int j=0;j<b.size();j++){double dx = a[i].first – b[b.size()-j-1].first;double dy = a[i].second – b[b.size()-j-1].second;if(dy >= d) break;d = min(d, sqrt(dx * dx + dy * dy));}b.push_back(a[i]);}return d;}void solve(){sort(A, A + N);double ans = closest_pair(A, N);if(ans >= 10000) cout << "INFINITY" << endl;else printf("%.4lf\n", ans);}int main(){while(scanf("%d", &N)!=EOF){if(N == 0)break;for(int i=0;i<N;i++)scanf("%lf%lf", &A[i].first, &A[i].second);solve();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
人之所以能，是相信能。
