P1257 平面上的最接近点对

题目

思路

详见加强加强版

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=4e5+10;
pair<int,int> a[maxn];
int n;
double d=1e16;
pair<int,int> vl[maxn],vr[maxn];
void read() { cin>>n;for(int i=1;i<=n;i++) cin>>a[i].first>>a[i].second; }
double dis2(pair<int,int> a,pair<int,int> b) { return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second); }
void solve(int l,int r){if(l==r) { swap(a[l].first,a[l].second);return; }int mid=l+r>>1;int x=a[mid].first;solve(l,mid),solve(mid+1,r);double dis=sqrt(d);int sl=0,sr=0;for(int i=l;i<=mid;i++) if(x-a[i].second<dis) vl[++sl]=a[i];for(int i=mid+1;i<=r;i++) if(a[i].second-x<dis) vr[++sr]=a[i];int p=1,q=0;for(int i=1;i<=sl;i++){while(p<=sr&&vl[i].first-vr[p].first>=dis) p++;while(q<sr&&vr[q+1].first-vl[i].first<dis) q++;for(int j=p;j<=q;j++) d=min(d,dis2(vl[i],vr[j]));}inplace_merge(a+l,a+mid+1,a+r+1);
}
signed main()
{read();sort(a+1,a+1+n);solve(1,n);printf("%.4lf",sqrt(d));return 0;
}