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 之后,
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 啥也别说了,隔空抱一个(激动