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
     
      #include
      
       #include
       
        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
        
         
          < int ConvexHull(){    sort(p,p+n);    int cnt=unique(p,p+n)-p;    int m=0;    for(int i=0;i
          
           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