用的分治,调整分治区间WA不同的点(有6,7,10)

P1429 平面最近点对(加强版)

w_II_j @ 2022-08-12 20:32:00

然后改为merg(l,mid-1)又WA了另一个不同的点; 下方为91分代码,与82分的差距仅在于18,19行

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
struct point{
    double x;
    double y;
}p[MAXN];int temp[MAXN];bool cmp(point a,point b){return a.x<b.x;}
double len(int a,int b)
{
    return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
int n;double dis;
double merg(int l,int r)
{
    if(l==r)return 1<<28;
    if(l==r-1)return len(l,r);
    int mid=(l-r)/2+r;
    double a=merg(l,mid-1);
    double b=merg(mid,r);
    dis=min(a,b);
    int k=0;
    for(int i=l;i<=r;i++)
    {
        if(fabs(p[i].x-p[mid].x)<=dis){
            temp[++k]=i;
        }
    }
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k&&fabs(p[temp[i]].y-p[temp[j]].y);j++)
            dis=min(dis,len(temp[i],temp[j]));
    }return dis;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
    sort(p+1,p+1+n,cmp);
    cout<<fixed<<setprecision(4)<<merg(1,n);
    return 0;
}

下方为82分代码(真的别的地方都一样)

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
struct point{
    double x;
    double y;
}p[MAXN];int temp[MAXN];bool cmp(point a,point b){return a.x<b.x;}
double len(int a,int b)
{
    return sqrt((p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y));
}
int n;double dis;
double merg(int l,int r)
{
    if(l==r)return 1<<28;
    if(l==r-1)return len(l,r);
    int mid=(l-r)/2+r;
    double a=merg(l,mid);
    double b=merg(mid+1,r);
    dis=min(a,b);
    int k=0;
    for(int i=l;i<=r;i++)
    {
        if(fabs(p[i].x-p[mid].x)<=dis){
            temp[++k]=i;
        }
    }
    for(int i=1;i<=k;i++){
        for(int j=i+1;j<=k&&fabs(p[temp[i]].y-p[temp[j]].y);j++)
            dis=min(dis,len(temp[i],temp[j]));
    }return dis;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
    sort(p+1,p+1+n,cmp);
    cout<<fixed<<setprecision(4)<<merg(1,n);
    return 0;
}

by w_II_j @ 2022-08-12 22:26:18

@hgzxgzx 抱(激动


上一页 |