计蒜客♂计蒜客♂计蒜客♂计蒜客

[模板]二维凸包

2019-04-01 19:38:19


#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
struct Vec2{
    double x,y;
    Vec2(){}
    Vec2(int _x,int _y){
        x = _x;
        y = _y;
    }
    inline Vec2 operator - (const Vec2 &a) const{
        return Vec2(x-a.x,y-a.y);
    }
    inline double disTo(const Vec2 &b){
        return sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));
    }
    inline double operator % (const Vec2 &a) const{
        //xmul
        return x*a.y - y*a.x;
    }
    inline bool operator < (const Vec2 &a) const{
        if(x == a.x) return y < a.y;
        return x < a.x;
    }
}Points[maxn];
int n;
int sta[maxn],psta=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&Points[i].x,&Points[i].y);
    sort(Points+1,Points+1+n);
    sta[++psta] = 1;
    sta[++psta] = 2;
    for(int i=3;i<=n;i++){
        Vec2 pre = Points[sta[psta]] - Points[sta[psta-1]];
        Vec2 now = Points[i] - Points[sta[psta]];
        while(pre % now < 0.0){
            if(psta == 1) break;
            --psta;
            pre = Points[sta[psta]] - Points[sta[psta-1]];
            now = Points[i] - Points[sta[psta]];
        }
        sta[++psta] = i;
    }
    int mid = psta;
    sta[++psta] = n;
    sta[++psta] = n-1;
    for(int i=n-2;i>=1;i--){
        Vec2 pre = Points[sta[psta]] - Points[sta[psta-1]];
        Vec2 now = Points[i] - Points[sta[psta]];
        while(pre % now < 0.0){
            if(psta == mid + 1) break;
            --psta;
            pre = Points[sta[psta]] - Points[sta[psta-1]];
            now = Points[i] - Points[sta[psta]];
        }
        sta[++psta] = i;
    }
    double ans = 0;
    for(int i=2;i<=psta;i++){
        ans += Points[sta[i]].disTo(Points[sta[i-1]]);
    }
    printf("%.2f\n",ans);
    return 0;
}