Codevs 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

计算几何

/*

计算几何第二题留念flag.

Jarvis O(NM)(M为凸包上的点的个数)

从最下面的一坨点找一个最左边的点.

然后以向右为基准扫描.

用叉积判断两点的位置关系.

重复上述步骤即可.

*/

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#define MAXN 100001

using namespace std;

int n,top;

double ans;

struct data{int x,y;}s[MAXN],a[MAXN];

bool cmp(const data &x,const data &y)

{

    if(x.y!=y.y) return x.y<y.y;

    return x.x<y.x;

}

bool chaji(const data &x,const data &y,const data &z)

{

    return (y.x-x.x)*(z.y-x.y)>(z.x-x.x)*(y.y-x.y);

}

double slove(double x1,double y1,double x2,double y2)

{

    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));

}

int main()

{

    scanf("%d",&n);

    for(int i=0;i<n;i++) scanf("%d%d",&a[i].x,&a[i].y);

    sort(a,a+n,cmp);

    s[0]=a[0];s[1]=a[1];top=1;

    for(int i=2;i<n;i++)

    {

        while(top&&!chaji(s[top],s[top-1],a[i])) top--;

        s[++top]=a[i];

    }

    int l=top;

    s[++top]=a[n-2];

    for(int i=n-3;i>=0;i--)

    {

        while(top!=l&&!chaji(s[top],s[top-1],a[i])) top--;

        s[++top]=a[i];

    }

    ans+=slove(s[0].x,s[0].y,s[top-1].x,s[top-1].y);

    for(int i=0;i<top-1;i++)

      ans+=slove(s[i].x,s[i].y,s[i+1].x,s[i+1].y);

      printf("%.1lf",ans);

      return 0;

}

巴特西

Codevs 1298 凸包周长

最新文章

热门文章