Wall---hdu1348(求凸包周长 模板)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1348

求凸包周长+2*PI*L；

#include <stdio.h>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

const int N = ;

const double eps = 1e-;

const double PI = acos(-);

struct point

{

    double x, y;

    point(){}

    point(double x, double y) : x(x), y(y) {}

    point friend operator - (const point &p1, const point &p2)///矢量p2p1;

    {

        return point(p1.x-p2.x, p1.y-p2.y);

    }

    double friend operator ^ (const point &p1, const point &p2)///p1×p2;

    {

        return p1.x*p2.y - p1.y*p2.x;

    }

};

point p[N], res[N];

double Dist(point p1, point p2)

{

    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));

}

int cmp1(point p1, point p2)///位置排序，找到最下方的；

{

    if(p1.y != p2.y)

        return p1.y < p2.y;

    return p1.x < p2.x;///若有多个下方的找左边的；

}

int cmp2(point p1, point p2)///极角排序；若极角相同，距离近的在前面；

{

    double k = (p1-p[])^(p2-p[]);

    if( k>eps || (fabs(k)<eps && Dist(p1, p[]) < Dist(p2, p[]) ))

        return ;

    return ;

}

int Graham(int n)///构造凸包,O(nlogn)

{

    res[] = p[];if(n == ) return ;

    res[] = p[];if(n == ) return ;

    int top = ;

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

    {

        while(top && ((res[top]-res[top-])^(p[i]-res[top-])) <= ) top--;

        ///当res[top-1]->res[top]->p[i]，出现右拐或直行时没说明res[top]不是凸包上的点；

        res[++top] = p[i];

    }

    return top+;

}

int main()

{

    int n, T;

    double L;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%lf", &n, &L);

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

            scanf("%lf %lf", &p[i].x, &p[i].y);

        sort(p, p+n, cmp1);///p[0]为最下方靠左的点；

        sort(p+, p+n, cmp2);///以p[0]为基点，按叉积进行排序；

        int cnt = Graham(n);///求凸包的顶点个数cnt，保存在res中，下标从0开始；

        double ans = Dist(res[], res[cnt-]);

        for(int i=; i<cnt; i++)

            ans += Dist(res[i], res[i-]);

        ans += PI**L;

        printf("%.0f\n", ans);

        if(T)puts("");

    }

    return ;

}