2015年4月21日 星期二

2015/04/21 凸包

/*
    求凸包的點數 和 周長
*/
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct xy
{
    double x, y;
    xy(double _x = 0, double _y = 0){ x = _x; y = _y; }

    bool operator<(const xy &p) const { return x < p.x || x-p.x == 0 && y < p.y; }
    xy operator-(const xy &p) const { return xy(x-p.x, y-p.y); }
    double operator%(const xy &p) const { return x*p.y-y*p.x; }

    static double dis(const xy &a, const xy &b)
    {
        double x = (a-b).x, y = (a-b).y;
        return sqrt(x*x+y*y);
    }
};

int N;
xy pt[1000000];

vector<xy> mk_tp()
{
    vector<xy> ans, re;
    #define rn re.size()

    for(int Ni = 0; Ni < N; Ni++)
    {
        while( rn >= 2 && (re[rn-1]-re[rn-2])%(pt[Ni]-re[rn-1]) <= 0 ) re.pop_back();
        re.push_back(pt[Ni] );
    }

    for(int ri = 0; ri < rn-1; ri++) ans.push_back(re[ri] );
    re.clear();

    for(int Ni = N-1; Ni >= 0; Ni--)
    {
        while( rn >= 2 && (re[rn-1]-re[rn-2])%(pt[Ni]-re[rn-1]) <= 0 ) re.pop_back();
        re.push_back(pt[Ni] );
    }

    for(int ri = 0; ri < rn-1; ri++) ans.push_back(re[ri] );
    re.clear();

    return ans;
}

int main()
{
    scanf("%d", &N);

    for(int Ni = 0; Ni < N; Ni++)
        scanf("%lf %lf", &pt[Ni].x, &pt[Ni].y);

    sort(pt, pt+N);
    vector<xy> v = mk_tp();

    double length = 0;

    for(int vi = 0; vi < v.size(); vi++)
        length += xy::dis(v[vi], v[(vi+1)%v.size()]);

    printf("%d %.10f\n", v.size(), length);
}

沒有留言:

張貼留言