求助
查看原帖
求助
428449
Amon_Xolotl楼主2023/7/24 21:27

为什么第一个数据点我在洛谷上测出来时788,但在在线IDE上测出来是793?

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=2e5+10;
int n,t=1;
db ans=1e20,res=-1e20-1e-4,esp=1e-4;
struct zjy
{
	 db x,y;
	 zjy(db x=0,db y=0) : x(x),y(y) {}
};
struct cmp_x
{
	bool operator()(const zjy &a,const zjy &b) const{
		return a.x<b.x||(a.x==b.x&&a.y<b.y);
	}
};
struct cmp_y
{
	bool operator()(const zjy &a,const zjy &b) const
	{
		return a.y<b.y;
	}
};
void upans(zjy a,zjy b)
{
	db dis=sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
	if(dis<ans)
	{
		ans=dis;
	}
}
zjy a[N],e[N];
db check(zjy a1,zjy a2,zjy b1,zjy b2)
{
	return (a2.x-a1.x)*(b2.y-b1.y)-(a2.y-a1.y)*(b2.x-b1.x);
}
db dist(zjy a,zjy b)
{
	return pow(a.x-b.x,2)+pow(a.y-b.y,2);
}
bool cmp(zjy p1,zjy p2)
{
	db tmp=check(e[1],p1,e[1],p2);
	if(tmp>0)
	{
		return true;
	}
	else if(tmp==0&&dist(e[0],p2)-dist(e[0],p1)>esp)
	{
		return true;
	}
	return false;
}
db compare(zjy a,zjy b,zjy c)
{
	return check(a,c,a,b);
}
multiset<zjy,cmp_y> s;
zjy Q[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%lf%lf",&a[i].x,&a[i].y);
		e[i].x=a[i].x,e[i].y=a[i].y;
		if(i>1&&(e[1].y-e[i].y>esp||(e[i].y==e[1].y&&e[1].x-e[i].x>esp)))
		{
			swap(e[1],e[i]);
		}
	}
	sort(a+1,a+n+1,cmp_x());
	int top=1;
	for(int i=1;i<=n;++i)
	{
		while(top<i&&a[i].x-a[top].x>ans)
		{
			s.erase(s.find(a[top++]));
		}
		for(auto c=s.lower_bound(zjy(a[i].x,a[i].y-ans));c!=s.end()&&c->y-a[i].y<ans;++c)
		{
			upans(*c,a[i]);
		}
		s.insert(a[i]);
	}
	sort(e+2,e+n+1,cmp);
	Q[1]=e[1];
	for(int i=2;i<=n;++i)
	{
		while(t>1&&check(Q[t-1],Q[t],Q[t-1],e[i])<=0)
		{
			--t;
		}
		Q[++t]=e[i];
	}
	Q[++t]=e[1];
    int p=2;
    Q[0]=Q[t];
	for(int i=0;i<=t;++i)
	{
		while(fabs(compare(Q[i],Q[i+1],Q[p+1]))-fabs(compare(Q[i],Q[i+1],Q[p]))>esp)
		{
			p=(p+1)%t;
		}
		res=max(res,max(dist(Q[i],Q[p]),dist(Q[i+1],Q[p])));
	}
	printf("%.2lf %.2lf",ans,sqrt(res));
	return 0; 
}
2023/7/24 21:27
加载中...