POJ - 1113 - Wall （凸包）

链接：

http://poj.org/problem?id=1113

题意：

求凸包，外加圆的周长

思路：

板子：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const double eps = 1e-7;
const double PI = 3.1415926;
struct Point
{
    double x,y;
    Point(double x =0,double y = 0):x(x),y(y) {}
};
int n ;
Point p[1200],s[1200];
double cross(Point a,Point b, Point c)
{
    return ((b.x - a.x) *(c.y-a.y)- (b.y - a.y)*(c.x - a.x));
}
double dis(Point a,Point b)
{
    return sqrt((a.x- b.x)*(a.x - b.x)+(b.y - a.y)*(b.y-a.y));
}
bool cmp(Point a,Point b)
{
    if(a.x != b.x ) return a.x < b.x;
    else
        return a.y < b.y;
}
bool cmp1(Point a,Point b)
{
    double m =cross(p[0],a,b);
    if(fabs(m- 0.0) <= eps)
    {
        if(dis(p[0],b)>dis(p[0],a))return true;
        return false;
    }
    else
    {
        if(m > 0) return true;
        else return false;
    }
}
int main()
{
    double l;
    while(cin>>n>>l)
    {
        for(int i = 0; i < n; i++)
            cin>>p[i].x>>p[i].y;
        sort(p,p+n,cmp);
        sort(p,p+n,cmp1);
        s[0].x = p[0].x;
        s[0].y = p[0].y;
        s[1].x = p[1].x;
        s[1].y = p[1].y;
        int top = 1;
        for(int i = 2; i < n; i++)
        {
            while(top>=1 && cross(s[top-1],s[top],p[i]) < 0)top--;
            s[++top] = p[i];
        }
        double sum = 0;
        for(int i = 0; i < top; i++)
            sum += dis(s[i],s[i+1]);
        sum += dis(s[0],s[top]);
        sum +=(2*PI*l);
        printf("%.f\n",sum);
    }
    return 0;
}