首页 > 代码库 > 1298 凸包周长

1298 凸包周长

1298 凸包周长

 

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
 
 
题目描述 Description

给出平面上n个点,求出这n个点形成的凸包的周长。

凸包的定义:能覆盖住这个n个点的最小凸多边形。

输入描述 Input Description

第一行一个整数n,接下来n行,每行两个整数x和y,表示一个点的坐标。

数据范围 1 <= n <= 100000

-10000<=x,y<=10000  

输出描述 Output Description

一行一个实数,表示凸包周长,保留一位小数.

样例输入 Sample Input

5

0 0

2 2

0 2

2 0

1 1

 

样例输出 Sample Output

8.0

数据范围及提示 Data Size & Hint

分类标签 Tags 点此展开 

 
计算几何
//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\n",ans);    return 0;}/*ConvexHull()段代码来自小白书P272 */

 

1298 凸包周长