LonelinessMan @ 2018-12-13 19:09:21
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<db,db> P;
const int maxn=200010;
const db inf=1E200;
P a[maxn];
int n;
inline db dis(db x1,db y1,db x2,db y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
db solve(int l,int r){
if(l==r)return inf;
int mid=(l+r)>>1;
db ret=min(solve(l,mid),solve(mid+1,r)),m=a[mid].first;
int t1=l,t2=mid+1,t=0;
vector<P>v,vt;
while(t1<=mid&&t2<=r){
if(a[t1].second<a[t2].second)v.push_back(a[t1]),++t1;
else v.push_back(a[t2]),++t2;
}
while(t1<=mid)v.push_back(a[t1]),++t1;
while(t2<=r)v.push_back(a[t2]),++t2;
for(int i=0;i<v.size();++i)a[l+i]=v[i];
for(int i=l;i<=r;++i){
if(fabs(a[i].first-m)>=ret)continue;
for(int j=vt.size()-1;j>=0;--j){
if(fabs(vt[j].second-a[i].second)>=ret)continue;
ret=min(ret,dis(a[i].first,a[i].second,vt[j].first,vt[j].second));
}
vt.push_back(a[i]);
}
return ret;
}
int main(){
freopen("a.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i].first>>a[i].second;
sort(a+1,a+1+n);
printf("%.4lf",solve(1,n));
return 0;
}
by LonelinessMan @ 2018-12-13 19:13:58
而且我的答案是偏小的。。。
by LonelinessMan @ 2018-12-13 19:30:41
我的答案是偏大的。。。说错了 if(fabs(a[i].first-m)>=ret)continue;删了就对了为什么啊
by LonelinessMan @ 2018-12-13 20:07:21
为什么把solve(l,mid)改成solve(l,mid-1)就对了。。
by w_II_j @ 2022-08-12 20:25:24
同...