如下是我这题的(从模板题复制过来的)旋转卡壳代码,过不了最后两个点,所以想请教如何写旋转卡壳是标准不会出错的。/kk
#include<bits/stdc++.h>
using namespace std;
#define N 100003
#define LL long long
#define INF 0x3f3f3f3f
#define PDD pair<double,double>
#define x first
#define y second
const double eps=1e-8;
int n,tp,stk[N];
double ans1=INF,ans2;
PDD h[N],p[N];
bool vis[N];
int sign(double x){
if(fabs(x)<eps) return 0;
if(x<0) return -1;
return 1;
}
int dcmp(double x,double y) //浮点数比较
{return sign(x-y);}
PDD operator- (PDD a,PDD b)
{return {a.x-b.x,a.y-b.y};}
double cross(PDD a,PDD b) //叉积
{return a.x*b.y-a.y*b.x;}
double area(PDD a,PDD b,PDD c) //向量ab,ac形成的平行四边形的有向面积
{return cross(b-a,c-a);}
double getd(PDD a,PDD b){
PDD d=a-b;
return sqrt(d.x*d.x+d.y*d.y);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&h[i].x,&h[i].y);
sort(h+1,h+n+1);
for(int i=1;i<=n;++i){ //求凸包下半部分
while(tp>=3&&sign(area(h[stk[tp-1]],h[stk[tp]],h[i]))<=0){
if(sign(area(h[stk[tp-1]],h[stk[tp]],h[i]))<0)
vis[stk[tp--]]=false;
else tp--;
}
stk[++tp]=i,vis[i]=true; //入栈并标记点在凸包上
}
vis[1]=false; //取消1号点标记从而使凸包封口
for(int i=n;i;--i){ //求凸包上半部分
if(vis[i]) continue;
while(tp>=3&&sign(area(h[stk[tp-1]],h[stk[tp]],h[i]))<=0)
tp--;
stk[++tp]=i;
}
tp--;
if(tp<=2) ans2=getd(h[0],h[n-1]); //如果所有点共线
else for(int i=1,j=3;i<=tp;++i){ //否则旋转卡壳
PDD a=h[stk[i]],b=h[stk[i+1]];
while(dcmp(area(a,b,h[stk[j]]),area(a,b,h[stk[j+1]]))<0)
j=j%tp+1;
ans2=max(ans2,max(getd(a,h[stk[j]]),getd(b,h[stk[j]])));
}
printf("%.2lf %.2lf\n",ans1,ans2); //ans1可忽略,ans2与答案不符
return 0;
}