ACM:旋转卡壳 凸包周长

旋转卡壳 凸包周长

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
int sign(double x) { // 符号函数
    if (fabs(x) < eps) return 0;//x是0
    if (x < 0) return -1;//x是负数
    return 1;//x是正数
}
struct Point{
    double x, y;
   Point(double x = 0, double y = 0) : x(x), y(y) { }
 	Point operator +(Point B){return Point(x+B.x,y+B.y);}
    Point operator -(Point B){return Point(x-B.x,y-B.y);}
    Point operator *(double k){return Point(x*k,y*k);}
    Point operator /(double k){return Point(x/k,y/k);}
    bool operator == (Point B){return sign(x-B.x)==0&&sign(y-B.x)==0;}
    bool operator <(Point B)//排序
{return sign(x-B.x)<0||sign(x-B.x)==0&&sign(y-B.y)<0;}

};
double cross(Point a, Point b){//外积（叉积）
//向量A与B张成的平行四边形的有向面积。B在A的逆时针方向为正。
//如果等0则，两个向量平行
     return a.x * b.y - b.x * a.y;
}
double area(Point a, Point b, Point c){
//计算向量AB与AC构成的平行四边形有向面积
     return cross(b-a, c-a);
}
double get_len(Point a,Point b){
	Point A=a-b;//两点所成线段距离
	double W=A.x*A.x+A.y*A.y;
		W=sqrt(W);
	return W;
}
const int N=1e5+10;
Point a[N];
int n,stk[N];
bool used[N];
vector<int>convex;
double andrew(){
	sort(a+1,a+1+n);//最左右两点属于凸包上点
	int top=0;
	for(int i=1;i<=n;i++){//凸包上链边
		while(top>=2){
			double B=area(a[stk[top-1]],a[i],a[stk[top]]);
			int A=sign(B);
 			if(A>=0)
			used[stk[top--]]=false;
			else break;
		}
	 stk[++top]=i;
	 used[i]=true;
	}
	for(int i=1;i<top;i++)//不加最右点
	convex.push_back(stk[i]);
	used[1]=false;used[n]=false;
	top=0;
	for(int i=n;i>=1;i--){//上链边
		if(used[i]) continue;
		while(top>=2){
			double B=area(a[stk[top-1]],a[i],a[stk[top]]);
			int A=sign(B);
			if(A>=0)
			used[stk[top--]]=false;
		else break;
		}
		stk[++top]=i;
		 used[i]=true;
	}
	for(int i=1;i<top;i++)//不加最左点
	convex.push_back(stk[i]);
	double res=0;
	for(int i=0;i<convex.size();i++){//围成圈的各个点
	  res+=get_len(a[convex[(i + 1) % convex.size()]] , a[convex[i]]);
	}
return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;	
	}
	double res=andrew();
	cout<<fixed<<setprecision(2)<<res;
}
signed main(){
solve();	
	return 0;
}