用的分治,调整分治区间WA不同的点(有6,7,10)
查看原帖
用的分治,调整分治区间WA不同的点(有6,7,10)
530142
w_II_j楼主2022/8/12 20:32

然后改为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;
}
2022/8/12 20:32
加载中...