为什么第一个数据点我在洛谷上测出来时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;
}