POJ 1113 凸包 - c++编程基础

易知
先求凸包，然后圆弧部分跟每个内角有关
经过计算发现圆弧总共加起来就是一个圆
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#define MAXN 111111  
#define MAXM 211111  
#define PI acos(-1.0)  
#define eps 1e-8  
#define INF 1000000001  
using namespace std;  
int dblcmp(double d)  
{  
    if (fabs(d) < eps) return 0;  
    return d > eps   1 : -1;  
}  
struct point  
{  
    double x, y;  
    point(){}  
    point(double _x, double _y):  
    x(_x), y(_y){};  
    void input()  
    {  
        scanf("%lf%lf",&x, &y);  
    }  
    double dot(point p)  
    {  
        return x * p.x + y * p.y;  
    }  
    double distance(point p)  
    {  
        return hypot(x - p.x, y - p.y);  
    }  
    point sub(point p)  
    {  
        return point(x - p.x, y - p.y);  
    }  
    double det(point p)  
    {  
        return x * p.y - y * p.x;  
    }  
    bool operator < (point a)const  
    {  
        return dblcmp(a.x - x) == 0   dblcmp(y - a.y) < 0 : x < a.x;  
    }  
  
}p[MAXN];  
struct line  
{  
    point a, b;  
    line(){}  
    line(point _a, point _b){ a = _a; b = _b;}  
};  
struct polygon  
{  
    int n;  
    point p[MAXN];  
    line l[MAXN];  
    double area;  
    double circum;  
    void input()  
    {  
        for(int i = 0; i < n; i++) p[i].input();  
    }  
    void getline()  
    {  
        for(int i = 0; i < n; i++)  
            l[i] = line(p[i], p[(i + 1) % n]);  
    }  
    void getarea()  
    {  
        area = 0;  
        int a = 1, b = 2;  
        while(b <= n - 1)  
        {  
            area += p[a].sub(p[0]).det(p[b].sub(p[0]));  
            a++;  
            b++;  
        }  
        area = fabs(area) / 2;  
    }  
    void getcircum()  
    {  
        circum = 0;  
        for(int i = 0; i < n; i++) circum += l[i].a.distance(l[i].b);  
    }  
}convex;  
bool conpoint(point p[],int n)  
{  
    for (int i = 1; i < n; i++)  
        if (dblcmp(p[i].x - p[0].x) != 0 ||  
                dblcmp(p[i].y - p[0].y) != 0)  
            return false;  
    return true;  
}  
bool conline(point p[],int n)  
{  
    for (int i = 2; i < n; i++)  
        if (dblcmp(p[1].sub(p[0]).det(p[i].sub(p[0])))  != 0)   return false;  
    return true;  
}  
void getconvex(point p[], int n, point res[], int& resn)  
{  
    resn = 0;  
    if (conpoint(p, n))  
    {  
        res[resn++] = p[0];  
        return;  
    }  
    sort(p, p + n);  
    if (conline(p,n))  
    {  
        res[resn++] = p[0];  
        res[resn++] = p[n - 1];  
        return;  
    }  
    for (int i = 0; i < n;)  
        if (resn < 2 || dblcmp(res[resn - 1].sub(res[resn - 2]).det(p[i].sub(res[resn - 1]))) >




 0)  
            res[resn++] = p[i++];  
        else --resn;  
    int top = resn - 1;  
    for (int i = n - 2; i >= 0;)  
        if (resn < top + 2 || dblcmp(res[resn - 1].sub(res[resn - 2]).det(p[i].sub(res[resn - 1]))) > 0)  
            res[resn++] = p[i--];  
        else --resn;  
    resn--;  
}  
double L;  
int n;  
int main()  
{  
    while(scanf("%d%lf", &n, &L) != EOF)  
    {  
        for(int i = 0; i < n; i++) p[i].input();  
        getconvex(p, n, convex.p, convex.n);  
        convex.getline();  
        convex.getcircum();  
        printf("%d\n", (int)(2 * L * PI + convex.circum + 0.5));  
    }  
    return 0;  
}