思路:
平面分治
inplace_merge()可以用来归并排序
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e4 + 5; const int INF = 0x3f3f3f3f; pair<double, double> p[N]; bool cmp(pair<double, double> a, pair<double, double> b) { return a.se < b.se; } double solve(pair<double, double> *a, int n) { if(n <= 1) return INF; int m = n/2; double mx = a[m].fi; double d = min(solve(a, m), solve(a+m, n-m)); inplace_merge(a+1, a+m+1, a+n+1, cmp); vector<pair<double, double> >vc; for (int i = 1; i <= n; i++) { if(abs(a[i].fi - mx) > d) continue; for (int j = 0; j < vc.size(); j++) { double dx = abs(a[i].fi - vc[vc.size()-1-j].fi); double dy = abs(a[i].se - vc[vc.size()-1-j].se); if(dy > d) break; d = min(d, sqrt(dx*dx + dy*dy)); } vc.pb(a[i]); } return d; } int main() { int n; while(~scanf("%d", &n) && n) { for (int i = 1; i <= n; i++) scanf("%lf %lf", &p[i].fi, &p[i].se); sort(p+1, p+n+1); double ans = solve(p, n); if(ans < 10000) printf("%.4f ", ans); else printf("INFINITY "); } return 0; }