涉及到凸包的一些小知识

1. 判断一个多边形是否为凸包
   选取一条边，沿着一个方向开始转。是凸包的话则每个边与之前一条边的叉积的符号是相同的。
   
   
2. 判断一个点是否在多边形内
   环顾角的概念：
   环顾这个点与每条边形成的有向角度，求和。
   形成角度—————关系
   ±2π—————————在多边形内
   0———————————在多边形外
   ±π——————————在多边形某个边上
   其余角度—————在多边形某个角上（角度相同）
   
   
3. 圆是否能放到凸包内
   计算圆心到葛格边的距离
   计算方法为：
   圆心与边端点形成的三角形。高 = 面积（两个向量叉乘） / 边长

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 1e3 + 5;
const double EPS = 1e-6;
const double PI = 3.1415926535897932384626;

struct Point
{
    Point() {}
    Point(double _x, double _y): x(_x), y(_y) {}
    double getDis(Point rhs)
    {
        double xx = rhs.x - x, yy = rhs.y - y;
        return sqrt(xx * xx + yy * yy);
    }

    void input(){scanf("%lf%lf", &x, &y);}

    double x, y;
};
double operator ^(Point lhs, Point rhs){return lhs.x * rhs.y - lhs.y * rhs.x;}
Point operator -(Point lhs, Point rhs){return Point(rhs.x - lhs.x, rhs.y - lhs.y);}
Point operator /(Point lhs, double rhs){return Point(lhs.x / rhs, lhs.y / rhs);}
Point operator *(Point lhs, double rhs){return Point(lhs.x * rhs, lhs.y * rhs);}
double operator *(Point lhs, Point rhs){return lhs.x * rhs.x + lhs.y * rhs.y;}

Point point[MAXN];
Point circle;
double r;
int n;


bool isConvex(Point *point)
{
    bool fst = true;
    double cmp;
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n, nxt2 = (i + 2) % n;
        double result = (point[nxt] - point[i]) ^ (point[nxt2] - point[nxt]);
        if(fst && fabs(result) >= EPS)
        {
            fst = false;
            cmp = result;
        }
        if(!fst && cmp * result < 0) return false;
    }
    return true;
}

bool isCenterInPolygon(Point *point, Point &center, double r)
{
    double degree = 0.0;
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n;
        double cosd = (point[i] - center) * (point[nxt] - center)
                       / center.getDis(point[i]) / center.getDis(point[nxt]);
        degree += acos(cosd);
    }

    if(fabs(fabs(degree) - 2.0 * PI) <= EPS)//in the polygon
        return true;
    else if(fabs(degree) <= EPS) //outside
        return false;
    else if(r <= EPS) return true;// on the polygon
    return false;
}

bool isRadiusFit(Point *point, Point &center, double r)
{
    for(int i = 0; i < n; ++i)
    {
        int nxt = (i + 1) % n;
        double area = fabs((point[i] - center) ^ (point[nxt] - center));
        double dis = area / (point[i].getDis(point[nxt]));
        if(dis <= r - EPS) return false;
    }
    return true;
}

int main()
{
    while(scanf("%d", &n) && n >= 3)
    {
        scanf("%lf", &r);
        circle.input();
        for(int i = 0; i < n; ++i)
        {
            point[i].input();
        }
        if(isConvex(point))
        {
            if(isCenterInPolygon(point, circle, r) &&
               isRadiusFit(point, circle, r))
            {
                puts("PEG WILL FIT");
            }
            else
            {
                puts("PEG WILL NOT FIT");
            }
        }
        else
        {
            puts("HOLE IS ILL-FORMED");
        }
    }

}