81分，WA了第二，第十一个点，求助！

siyue @ 2021-01-26 13:51:08

#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;
}

by Remake_ @ 2021-01-26 13:56:13

你需要加上一点玄学

by big_news @ 2021-01-26 14:20:13

这题不是随机化

by siyue @ 2021-01-26 15:00:00

什么玄学？蒟蒻听不懂

by fffngzzh @ 2021-01-27 14:08:54

@siyue 玄学就是要碰运气……

by 滑蒻稽 @ 2021-02-21 12:08:14

同错#2和#11，同二分，不知道您解决了没有

by 滑蒻稽 @ 2021-02-21 13:15:38

#include <bits/stdc++.h>
#define INF 2e9
#define ll long long

using namespace std;
const int N=2e5+5;
int n,temp[N],p;
struct point
{
    int x,y;
}a[N];

bool cmp(const point &a,const point &b)
{
    if(a.x==b.x) return a.y<b.y;
    else return a.x<b.x;
}

double dist(const int &l,const int &r)//计算2点距离 
{
    double e1=a[l].x-a[r].x,e2=a[l].y-a[r].y;
    return sqrt(e1*e1+e2*e2);
}

double solve(const int &l,const int &r)//求解l号点到r号点 
{
    if(l==r) return INF;
    if(l+1==r) return dist(l,r);
    int mid=(l+r)>>1;
    double d1=solve(l,mid),d2=solve(mid+1,r);
    double d=(d1<d2)?d1:d2;//点对完整落在2边的最小值 
    p=0;
    for(int i=l;i<=r;i++)
    {
        if(fabs(a[i].x-a[mid].x)<=d)
        {
            temp[++p]=i;
        }
    } 
    for(int i=1;i<=p;i++)
    {
        for(int k=i+1;k<=p;k++)
        {
            if(a[temp[k]].x-a[temp[i]].x>d) break;
            if(fabs(a[temp[k]].y-a[temp[i]].y)>d) continue;
            d=min(d,dist(temp[i],temp[k]));
        }
    }
    return d;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);  
    }
    sort(a+1,a+n+1,cmp);
    printf("%.4f",solve(1,n));

    return 0;
}

我对了,这是我的代码,希望能帮到您

by siyue @ 2021-02-23 21:23:37

@滑蒻稽 谢谢dalao