求助标准的旋转卡壳写法(代码有注释)
查看原帖
求助标准的旋转卡壳写法(代码有注释)
239895
Yusani_huh楼主2022/7/18 20:49

如下是我这题的(从模板题复制过来的)旋转卡壳代码,过不了最后两个点,所以想请教如何写旋转卡壳是标准不会出错的。/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;
}
2022/7/18 20:49
加载中...