81分,WA了第二,第十一个点,求助!
查看原帖
81分,WA了第二,第十一个点,求助!
118296
siyue楼主2021/1/26 13:51

我是用二分做的,不知道为什么错了。

#include <bits/stdc++.h>
using namespace std;
int n;
struct node
{
    double x,y;
    bool operator <(const node z)const
    {
        return x<z.x;
    }
} a[400005],b[400005];
double dist(node x,node y)
{
    return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));
}
double dfs(int l,int r)
{
    if(l>=r)
        return 1e20;
    int mid=(l+r)>>1,len=0;
    double res=min(dfs(l,mid),dfs(mid+1,r)),mid_x=a[mid].x;
    int i=l,j=mid+1,k=l;
    while(i<=mid&&j<=r)
        if(a[i].y<=a[j].y)
            b[k++]=a[i++];
        else
            b[k++]=a[j++];
    while(i<=mid) b[k++]=a[i++];
    while(j<=r) b[k++]=a[j++];
    for(i=l; i<=r; i++)
        a[i]=b[i];
    for(i=l; i<=r; i++)
    {
        if(a[i].x<=mid_x+res+1e-6&&a[i].x>=mid_x-res-1e-6)
            b[++len]=a[i];
    }
    for(i=1; i<=len; i++)
        for(j=i+1; j<=len&&b[j].y-b[i].y<=res; j++)
            res=min(res,dist(b[i],b[j]));
    return res;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j;
    cin>>n;
    for(i=1; i<=n; i++)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    printf("%.4f\n",dfs(1,n));
    return 0;
}

2021/1/26 13:51
加载中...