poj 1584 A Round Peg in a Ground Hole

這個題需要多個計算幾何算法。第一個是判斷一系列點是否能夠構成凸多邊形，第二個是判斷一個點是否在一個簡單多邊形內部，
第三個是求一個點到一條線段（或者說直線）的距離，第四個是判斷一個圓是否則一個凸多邊形內部。
   其實，我是要判斷一個圓是否則一個凸多邊形內部而用到算法二和三。其實，有不需要判斷圓心是否則多邊形內部的算法。
   算法一的思想，求所有邊的偏轉方向，必須都是逆時針或者順時針偏轉。算法二則是我前面發的那篇改進弧長法判斷點和多邊形的關系，
算法三尤其簡單，直線上面取2點，用叉積求出這三點構成的三角形面積的2倍，再除以底邊。算法四則是先判斷圓心在多邊形內部，然後
判斷圓心到所有邊的距離要大於圓的半徑。
   貼出代碼，純粹為了以後作為模版使用等，防止遺忘，方便查找，其實現在也能手敲出來了。

 代碼如下：
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;

const double fPre = 1e-8;
int DblCmp(double fD)
{
    if (fabs(fD) < fPre)
    {
        return 0;
    }
    else
    {
        return fD > 0 ? 1 : -1;
    }
}

struct Point
{
    double x, y;
    bool operator == (const Point& p)
    {
        return DblCmp(x - p.x) == 0 && DblCmp(y - p.y) == 0;
    }
};

Point operator-(const Point& a, const Point& b)
{
    Point p;
    p.x = a.x - b.x;
    p.y = a.y - b.y;
    return p;
}

double Det(double fX1, double fY1, double fX2, double fY2)
{
    return fX1 * fY2 - fX2 * fY1;
}

double Cross(Point a, Point b, Point c)
{
    return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}

bool IsConvexPolygon(vector<Point>& vp)
{
    int nN = vp.size();
    int nDirection = 0;
    bool bLine = true;//避免所有點共線
    for (int i = 0; i < nN; ++i)
    {
        int nTemp = DblCmp(Cross(vp[i], vp[(i + 1) % nN], vp[(i + 2) % nN]));
        if (nTemp)
        {
            bLine = false;
        }
        //這次的方向和上次的方向必須是相同的或者是3點和3點以上共線的情況
        if (nDirection * nTemp < 0)
        {
            return false;
        }
        nDirection = nTemp;
    }
    return bLine == false;
}

int GetQuadrant(Point p)
{
    return p.x >= 0 ? (p.y >= 0 ? 0 : 3) : (p.y >= 0 ? 1 : 2);
}

bool IsPtInPolygon(vector<Point>& vp, Point p)
{
    int nN = vp.size();
    int nA1, nA2, nSum = 0;
    int i;
   
    nA1 = GetQuadrant(vp[0] - p);
    for (i = 0; i < nN; ++i)
    {
        int j = (i + 1) % nN;
        if (vp[i] == p)
        {
            break;
        }
        int nC = DblCmp(Cross(p, vp[i], vp[j]));
        int nT1 = DblCmp((vp[i].x - p.x) * (vp[j].x - p.x));
        int nT2 = DblCmp((vp[i].y - p.y) * (vp[j].y - p.y));
        if (!nC && nT1 <= 0 && nT2 <= 0)
        {
            break;
        }
        nA2 = GetQuadrant(vp[j] - p);
        switch ((nA2 - nA1 + 4) % 4)
        {
            case 1:
                nSum++;
                break;
            case 2:
                if (nC > 0)
                {
                    nSum += 2;
                }
                else
                {
                    nSum -= 2;
                }
                break;
            case 3:
                nSum--;
                break;
        }
        nA1 = nA2;
    }
   
    if (i < nN || nSum)
    {
        return true;
    }
    return false;
}

double PtDis(Point a, Point b)
{
    return sqrt((a.x - b.x) * (a.x - b.x) + (b.y - a.y) * (b.y - a.y));
}
//點p到直線ab的距離
//h = (2 * Spab) / |ab|
double GetDis(Point a, Point b, Point p)
{
    return fabs(Cross(a, b, p)) / PtDis(a, b);
}

bool IsCircleInPolygon(vector<Point>& vp, Point p, double fR)
{
    if (!IsPtInPolygon(vp, p))
    {
        return false;
    }
   
    int nN = vp.size();
    for (int i = 0; i < nN; ++i)
    {
        if (GetDis(vp[i], vp[(i + 1) % nN], p) < fR)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    int nN;
    double fR, fPx, fPy;
    vector<Point> vp;
    Point p;
   
    while (scanf("%d%lf%lf%lf", &nN, &fR, &fPx, &fPy), nN >= 3)
    {
        vp.clear();
        for (int i = 0; i < nN; ++i)
        {
            scanf("%lf%lf", &p.x, &p.y);
            vp.push_back(p);
        }    www.2cto.com
       
        if (IsConvexPolygon(vp))
        {
            p.x = fPx;
            p.y = fPy;
            if (IsCircleInPolygon(vp, p, fR))
            {
                printf("PEG WILL FIT\n");
            }
            else
            {
                printf("PEG WILL NOT FIT\n");
            }
        }
        else
        {
            printf("HOLE IS ILL-FORMED\n");
        }
    }
   
    return 0;
}