首页 > 代码库 > 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 凸包周长
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。