用的分治,调整分治区间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 hgzxgzx @ 2022-08-12 20:43:14

1.我看您在分治过程中没有体现排序,主程序里应该把y作为第二关键字排序

2.返回条件建议改为

if(l+1==r) return ...
if(l+2==r) return ...

by hgzxgzx @ 2022-08-12 21:47:01

@w_II_j 抱歉,我刚刚的话具有一定的误导性(我自己都卡住了

您有些细节还是没有弄得很明白,建议再去看看博客,比如取 mid 之后,x\in[mid-dis,mid+dis] 的点是要按照纵坐标的升序来排序的,目的是为了确保复杂度正确


by w_II_j @ 2022-08-12 21:48:36

@hgzxgzx okok谢调,这就去再试


by hgzxgzx @ 2022-08-12 21:50:06

@w_II_j 抱歉啊,我刚刚没有at您


by hgzxgzx @ 2022-08-12 21:50:39

@w_II_j AC了麻烦通知我一声(心里怪痒痒的


by hgzxgzx @ 2022-08-12 21:59:03

@w_II_j 那个,我刚刚说在主程序里这么排是错的(尬


by w_II_j @ 2022-08-12 22:19:48

@hgzxgzx 啊啊啊啊啊啊啊啊谢谢谢谢我过了终于过了


by hgzxgzx @ 2022-08-12 22:22:29

@w_II_j 痛哭流涕,激动


by w_II_j @ 2022-08-12 22:22:45

@hgzxgzx 一共有两个问题,一是里面没有排序的问题,二是29行一个非常脑残的循环判断没写完的问题...总之谢谢dalao指教


by hgzxgzx @ 2022-08-12 22:24:04

@w_II_j 啥也别说了,隔空抱一个(激动


| 下一页