平面距离最短的三个点 (分治)

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define ll long long
#define db double
#define rg register int

using namespace std;

const db inf=1e16;

struct su{
    db x,y;
}a[200005],b[200005];

db xx,yy;
int n;

inline int qr(){
    char ch; int sign=1;
    while((ch=getchar())<'0'||ch>'9')
        if(ch=='-')sign=-1;
    int res=ch^48;
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+(ch^48);
    return res*sign;
}

inline bool cmp_x(su x,su y){return x.x<y.x;}
inline bool cmp_y(su x,su y){return x.y<y.y;}

inline db dis2(su x,su y){
    xx=(y.x-x.x),yy=(y.y-x.y);
    return sqrt(xx*xx+yy*yy);
}

inline db dis3(su x,su y,su z){
    return dis2(x,y)+dis2(x,z)+dis2(y,z);
}

inline db find(int l,int r){
    if(l+1>=r)return inf;
    int mid=(l+r)>>1;
    db d=min(find(l,mid),find(mid+1,r));
    while(a[l].x+d<a[mid].x)++l;
    while(a[r].x-d>a[mid].x)--r;
    int t=0;
    for(rg i=l;i<=r;++i)b[++t]=a[i];
    sort(b+1,b+t+1,cmp_y);
    for(rg i=1;i<=t;++i)
        for(rg j=i+1;j<=t;++j)
            if(b[j].y-b[i].y>=d)break;
            else for(rg k=j+1;k<=t;++k)
                     if(b[k].y-b[i].y>=d)break;
                     else d=min(d,dis3(b[i],b[j],b[k])/2);
    return d;
}

int main(){
    freopen("math.in","r",stdin);
    freopen("math.out","w",stdout);
    n=qr();
    for(rg i=1;i<=n;++i)
        a[i].x=qr(),a[i].y=qr();
    sort(a+1,a+n+1,cmp_x);
    printf("%.6lf\n",find(1,n)*2);
    return 0;
}
上一篇:codeforces contest 1111


下一篇:LG3374 【模板】树状数组 1