考虑分治
首先我们按照x轴排序，然后我们要求每段处理时y轴有序
然后排除一些不可能的情况后暴力统计就好了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=200005;
int n;
double ans=1e10;
struct Point{
int x,y;
friend bool operator<(Point A,Point B){return A.y<B.y;}
}poi[N],_point[N];
bool cmp(Point A,Point B){return A.x<B.x;}
double Abs(int x){return x>0?(double)x:(double)-x;}
double Di(Point A,Point B){return sqrt((double)(A.x-B.x)*(A.x-B.x)+(double)(A.y-B.y)*(A.y-B.y));}
void Solve(int l,int r){
if(l==r)return;
if(l+1==r){if(poi[r]<poi[l])swap(poi[l],poi[r]);return;}
int mid=l+r>>1,tp=poi[mid].x;
Solve(l,mid);Solve(mid+1,r);
int l1=l,l2=mid+1;
for(int i=l;i<=r;i++){
if(l2>r||(l1<=mid && poi[l1]<poi[l2]))_point[i]=poi[l1++];
else _point[i]=poi[l2++];
}
memcpy(poi+l,_point+l,sizeof(Point)*(r-l+1));
for(int i=l,tail=l;i<=r;i++){
if(Abs(poi[i].x-tp)<ans/2.0){
while(poi[i].y-poi[tail].y>ans/2.0)tail++;
for(int j=tail;j<i-1;j++)if(Abs(poi[j].x-tp)<ans/2.0)if(poi[i].y-poi[j].y<ans/2.0)for(int k=j+1;k<i;k++)ans=min(ans,Di(poi[i],poi[j])+Di(poi[i],poi[k])+Di(poi[j],poi[k]));
}
}
}
int main(){
freopen("2458.in","r",stdin);
freopen("2458.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d %d",&poi[i].x,&poi[i].y);
sort(poi+1,poi+n+1,cmp);
Solve(1,n);
printf("%lf\n",ans);
return 0;
}
评论 (0)
