刚入门分治,求大佬教改代码
  • 板块学术版
  • 楼主Durancer
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/9/16 18:18
  • 上次更新2023/11/5 13:07:46
查看原帖
刚入门分治,求大佬教改代码
230804
Durancer楼主2020/9/16 18:18
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
using namespace std;
struct node{
	double x;
	double y;
};
node a[200009];
int n;
double cmp(node x_,node y_)
{
	if(x_.x!=y_.x)
	{
		return x_.x<y_.x;
	}
	else return x_.y<y_.y;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	if(n==2)
	{
		double kkk=sqrt((a[1].x-a[2].x)*(a[1].x-a[2].x)+(a[1].y-a[2].y)*(a[1].y-a[2].y));
		printf("%.4lf",kkk);
		return 0;
	}
	sort(a+1,a+1+n,cmp);
	/*for(int i=1;i<=n;i++)
	{
		cout<<a[i].x<<" "<<a[i].y<<endl;
	}*/
	double l=a[1].x;
	double r=a[n].x;
	double mid=(l+r)/2;
	int bk;
	for(int i=1;i<=n;i++)
	{
		if(a[i].x>=mid)
		{
				bk=i-1;//这个地方本来是n-1,看着不对,就改过来了,交了一遍又多错了一个点
				break;
		} 
	}//1-bk为左边区间,bk+1为右边区间
	double min_front=0x7fffffff,min_last=0x7fffffff;
	for(int i=1;i<=bk;i++)
	{
		if(bk==1)
		{
			min_front=0;
			break;
		}
		for(int j=1;j<=bk;j++)
		{
			if(i!=j)
			{
				double kx=a[i].x-a[j].x;
				double ky=a[i].y-a[j].y;
				double gan=sqrt(kx*kx+ky*ky);
				min_front=min(min_front,gan);
			}
		}
	}//寻找两个区间的最小值 
	for(int i=bk+1;i<=n;i++)
	{
		if(bk+1==n)
		{
			min_last=0;
			break;
		}
		for(int j=bk+1;j<=n;j++)
		{
			if(i!=j)
			{
				double ox=a[i].x-a[j].x;
				double oy=a[i].y-a[j].y;
				double gand=sqrt(ox*ox+oy*oy);
				min_last=min(min_last,gand);
			}
		}
	}
	double ans;
	if(min_front==0)
	{
		ans=min_last;
	}
	else if(min_last==0)
	{
		ans=min_front;
	} 
	else ans=min(min_front,min_last);//如果为0则说明只有一个值;
	//则就给ans赋上另一个值 
	if(int(ans)==0)
	{
		ans=0x7fffffff;
	}
	int x_front=bk,x_last=bk+1;
	for(int i=bk;i>=1;i--)
	{
		if(mid-a[i].x>ans)
		{
			x_front=i+1;
			break;
		}	
	} 
	for(int i=bk+1;i<=n;i++)
	{
		if(a[i].x-mid>ans)
		{
			x_last=i-1;
			break;
		}
	}//找完两个独立的区间则再去找跨越两个区间的对点,并且他们到mid的横坐标差值应该
	//小于ans 
	double ans_cmp=0x7fffffff;
	for(int i=x_front;i<=bk;i++)
	{
		for(int j=x_last;i>=bk+1;i--)
		{
			double x_=a[i].x-a[j].x;
			double y_=a[i].y-a[j].y;
			double gandf=sqrt(x_*x_+y_*y_);
			ans_cmp=min(ans_cmp,gandf);
		} 
	}
	if(ans_cmp>ans)
	{
		printf("%.4f",ans);
	}
	else printf("%.4f",ans_cmp);
	return 0;
}
2020/9/16 18:18
加载中...