数据怎么回事?归并乱打过了?
查看原帖
数据怎么回事?归并乱打过了?
1220105
20230332fuben楼主2024/1/4 23:01
#include<iostream>
#include<algorithm> 
#include<cmath>
#include<vector>
using namespace std;
typedef  long double ld;
int n,cnt=0;
	struct inf
	{
		ld x,y;
	}node[200020],t[200020],tem[200020];
ld dis(ld x1,ld y1,ld x2,ld y2)
{	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

bool cmp(inf i,inf j)
{
	if(i.x!=j.x)return i.x<j.x;
	else return i.y<j.y;
}
bool cmpy(inf i,inf j)
{
	return i.y<j.y;
}
void merge(int l,int r)
{
	if(l==r)return ;
	int mid=(l+r)>>1;
	merge(l,mid),merge(mid+1,r);
	for(int a=l,i=l,j=mid+1;a<=r;a++)
	{
		if(j==r+1) tem[a]=node[i++];
		else if(i==mid+1) tem[a]=node[j++];
		else 
		{
			if(node[i].x!=node[j].x)
			{
				if(node[i].x<node[j].x)tem[a]=node[i++];
				else tem[a]=node[j++];
			}
			else 
			{
				if(node[i].y<node[j].y)tem[a]=node[i++];
				else tem[a]=node[j++];				
			}
		}
	}
	for(int a=l;a<=r;a++)node[a]=tem[a];	
}
void mergesort(int l,int r)
{
	if(l==r)return ;
	int mid=(l+r)>>1;
	mergesort(l,mid),mergesort(mid+1,r);
	for(int a=l,i=l,j=mid+1;a<=r;a++)
	{
		if(j==r+1) tem[a]=t[i++];
		else if(i==mid+1) tem[a]=t[j++];
		else 
		{
			if(node[i].y<node[j].y) tem[a]=t[i++];  //这里
//			if(t[i].y<t[j].y) tem[a]=t[i++]; 
			else tem[a]=t[j++];
		}
	}
	for(int a=l;a<=r;a++)t[a]=tem[a];
}
ld solve(int l,int r)
{
	if(l==r)return 2099999999.9;
	if(l+1==r)return dis(node[l].x,node[l].y,node[r].x,node[r].y);
	int mid=(l+r)>>1,cnt=1;
	ld d=min(solve(l,mid),solve(mid+1,r));
	for(int a=l;a<=r;a++)
		if(fabs(node[a].x-node[mid].x)<d) t[cnt++]=node[a];
	mergesort(0,cnt-1);
	for(int a=0;a<cnt-1;a++)	
		for(int b=a+1;b<cnt&&fabs(t[b].y-t[a].y)<d;b++)
			d=min(d,dis(t[a].x,t[a].y,t[b].x,t[b].y));
	cnt=0;
	return d;
}
int main(void)
{
	scanf("%d",&n);
	for(int a=1;a<=n;a++)
		scanf("%Lf%Lf",&node[a].x,&node[a].y);
	merge(1,n);
	cout.setf(ios_base::fixed);
	cout.precision(4);
	cout<<solve(1,n);
	return 0;
}

第60行(标记处)那里我是给t数组归并,写成了node,居然过了,反应过来我就改成t,改成正确的居然过不了!!!!大佬们为什么

2024/1/4 23:01
加载中...