平面最近点对
cpp
Point tmp[N];
void Merge(int l,int r,vector<Point> &a){
int mid=l+r>>1;
int i=l,j=mid+1;
int k=l;
while(i<=mid&&j<=r){
if(a[i].y<a[j].y)tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
while(i<=mid)tmp[k++]=a[i++];
while(j<=r)tmp[k++]=a[j++];
for(int i=l;i<=r;i++)a[i]=tmp[i];
}
double NearestPointDis(int l,int r,vector<Point> &a){
if(l>=r)return LLONG_MAX;
if(l+1==r){
if(a[l].y>a[r].y)swap(a[l],a[r]);
return (a[l]-a[r]).dis();
}
int mid=l+r>>1;
int t=a[mid].x;
double d=min(NearestPointDis(l,mid,a),NearestPointDis(mid+1,r,a));
Merge(l,r,a);
vector<int> pos;
for(int i=l;i<=r;i++){
if(1ll*(a[i].x-t)*(a[i].x-t)<d)pos.push_back(i);
}
for(int i=0;i<pos.size();i++){
for(int j=i+1;j<pos.size()&&1ll*(a[pos[i]].y-a[pos[j]].y)*(a[pos[i]].y-a[pos[j]].y)<d;j++){
d=min(d,(a[pos[i]]-a[pos[j]]).dis());
}
}
return d;
}