poj1113

题意：在一个多边形宫殿外造围墙，要求与宫殿与围墙各处至少保持l英尺，求围墙最小长度。

分析：凸包模板题，N次WA，百度空间里找到一组数据让程序出现runtime error，发现是Graham_scan里的while循环的结束条件缺少判断栈里的元素个数是否大于1。

#include <cstdio>
#include <cmath>
#include <algorithm>
#define vector point
using std::sort;
using std::swap;
const double PI = acos(-1.00);
struct point
{
    int x,y;
    point(int xx = 0,int yy = 0)
    {
        x = xx;
        y = yy;
    }
    point operator - (point s)
    {
        return point(x - s.x, y - s.y);
    }
    double len()
    {
        return sqrt(x * x + y * y + 0.0);
    }
    int len2()
    {
        return x * x + y * y;
    }
};

point p[1010];
int n,l,hull_list[1010];

int cross_product(vector v1,vector v2)
{
    return v1.x * v2.y - v1.y * v2.x;
}

bool cmp(point& a,point& b)
{
    int cp = cross_product(vector(a - p[0]),vector(b - p[0]));
    if(cp > 0 || (cp == 0 && vector((a - p[0])).len2() < vector((b - p[0])).len2() ) )
        return true;
    else
        return false;
}
//基点取p[0]，逆时针扫描，返回凸包上的点数
int Graham_scan()
{
    int top = 1;
    sort(p + 1,p + n,cmp);
    hull_list[0] = 0;
    hull_list[1] = 1;
    for(int i = 2;i < n;i++)
    {
        while(top >= 1 && cross_product(vector(p[hull_list[top]] - p[hull_list[top - 1]]),vector(p[i] - p[hull_list[top]])) <= 0)
            top--;
        hull_list[++top] = i;
    }
    return top + 1;
}

int main()
{
    int m;
    while(~scanf("%d%d",&n,&l))
    {
        int lowest = 0;
        for(int i = 0;i < n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            if(p[lowest].y > p[i].y)
                lowest = i;
        }

        swap(p[0],p[lowest]);
        m = Graham_scan();

        double len = 0;
        for(int i = 1;i < m;i++)
            len += (p[hull_list[i]] - p[hull_list[i - 1]]).len();
        len += (p[hull_list[0]] - p[hull_list[m - 1]]).len();
        printf("%d\n",(int)(len + 2.0 * l * PI + 0.5));
    }
    return 0;
}