题目描述 Description
给出平面上n个点,求出这n个点形成的凸包的周长。
凸包的定义:能覆盖住这个n个点的最小凸多边形。
输入描述 Input Description
第一行一个整数n,接下来n行,每行两个整数x和y,表示一个点的坐标。
数据范围 1 <= n <= 100000
-10000<=x,y<=10000
//Andrew算法
//核心思想:(以下凸包为例)顺向,左边就拐,否则后撤,直到能左拐。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+5;
const double eps=1e-10;
struct Vector{
double x,y;
Vector(double x=0,double y=0):x(x),y(y){}
}p[N],ch[N];int n;
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}//向量加法
Vector operator - (Vector A,Vector B){return Vector(A.x-B.x,A.y-B.y);}//向量减法
Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}//向量乘以标量
Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}//向量除以标量
bool operator < (const Vector &a,const Vector &b){//点的坐标排序
return a.x==b.x?a.y<b.y:a.x<b.x;
}
int dcmp(double x){//三态函数,减少精度问题
if(fabs(x)<eps) return 0;
else return x<0?-1:1;//忘写return WA*1
}
bool operator ==(const Vector &a,const Vector &b){//判断同一个点
return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}//向量点积
double Length(Vector A){return sqrt(Dot(A,A));} //向量长度,点积
double Angle(Vector A,Vector B){return acos(Dot(A,B)/Length(A)/Length(B));}//向量转角,逆时针,点积
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//向量叉积
double Area2(Vector A,Vector B,Vector C){return Cross(B-A,C-A);}//三角形有向面积的两倍
//计算凸包,输入点数组p,不重复个数cnt,输出点数组ch。函数返回凸包顶点个数。
//如果不希望在凸包的边上有输入点,把两个 <=改成 <
int ConvexHull(){
sort(p,p+n);
int cnt=unique(p,p+n)-p;
int m=0;
for(int i=0;i<cnt;i++){
while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
int k=m;
for(int i=cnt-2;i>=0;i--){
while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
ch[m++]=p[i];
}
if(cnt>1) m--;
return m;
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
int c=ConvexHull();double ans=0;
for(int i=0;i<c;i++) ans+=Length(ch[i]-ch[i+1]);
printf("%.1lf
",ans);
return 0;
}
/*
ConvexHull()段代码来自小白书P272
*/