poj 3130 How I Mathematician Wonder What You Are!

半平面交的一個題，也是求多邊形的核心。求出這個好像也可以用於解決一些線性規劃問題。我用的是N*N的基本算法，每加入一條直線，
就對原來求出的半平面交進行處理，產生新的核心。
   代碼參照台灣的一個網站演算法筆記上的內容和代碼。表示這個網站巨不錯，求凸包的算法也參照了這個網站上的內容和代碼。
   
   代碼思路主要是：先讀入所有的多邊形頂點，放入一個vector（vp）裡面，然後對多邊形的每條邊求一個半平面。剛開始的時候，用一個
vector（Polygon）保存代表上下左右四個無限遠角的四個點，表示原始的半平面。然後，用讀入的多邊形的每條邊去切割原來的半平面。
切割的過程是，如果原來（Polygon）中的點在當前直線的指定一側，那麼原來的點還是有效的。如果原來的點和它相鄰的下一個點與當前
直線相交，那麼還需要把交點加入Polygon集合。
   還有求交點的方法比較奇葩，類似於黑書上面的那種根據面積等分的方法。

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

double fPre = 1e-8;
struct Point
{
    double x;
    double y;
    Point(){}
    Point(double fX, double fY)
    {
        x = fX, y = fY;
    }
};
typedef vector<Point> Polygon;
typedef pair<Point, Point> Line;
Point operator+(const Point& a, const Point& b)
{
    Point t;
    t.x = a.x + b.x;
    t.y = a.y + b.y;
    return t;
}

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

Point operator*(Point a, double fD)
{
    Point t;
    t.x = a.x * fD;
    t.y = a.y * fD;
    return t;
}

int DblCmp(double fD)
{
    return fabs(fD) < fPre ? 0 : (fD > 0 ? 1 : -1);
}

double Det(double fX1, double fY1, double fX2, double fY2)
{
    return fX1 * fY2 - fX2 * fY1;
}
//3點叉積
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);
}
//向量叉積
double Cross(Point a, Point b)
{
    return a.x * b.y - a.y * b.x;
}

//求直線交點的一種簡便方法
//平行四邊形面積的比例等於高的比例
Point Intersection(Point a1, Point a2, Point b1, Point b2)
{
    Point a = a2 - a1;
    Point b = b2 - b1;
    Point s = b1 - a1;
   
    return a1 + a * (Cross(b, s) / Cross(b, a));
}

Polygon HalfPlane(Polygon& pg, Point a, Point b)
{
    Polygon pgTmp;
    int nN = pg.size();
    for (int i = 0; i < nN; ++i)
    {
        double fC = Cross(a, b, pg[i]);
        double fD = Cross(a, b, pg[(i + 1) % nN]);
        if (DblCmp(fC) >= 0)
        {
            pgTmp.push_back(pg[i]);
        }
        if (fC * fD < 0)
        {
            pgTmp.push_back(Intersection(a, b, pg[i], pg[(i + 1) % nN]));
        }
    }
    return pgTmp;
}

int main()
{
    int nN;
    Point p;
    vector<Point> vp;
    Polygon pg;
   
    while (scanf("%d", &nN), nN)
    {
        vp.clear();
        for (int i = 0; i < nN; ++i)
        {
            scanf("%lf%lf", &p.x, &p.y);
            vp.push_back(p);
        }
        pg.clear();
        pg.push_back(Point(-1e9, 1e9));
        pg.push_back(Point(-1e9, -1e9));
        pg.push_back(Point(1e9, -1e9));
        pg.push_back(Point(1e9, 1e9));
        for (int i = 0; i < nN; ++i)
        {
            pg = HalfPlane(pg, vp[i], vp[(i + 1) % nN]);
            if (pg.size() == 0)
            {
                printf("0\n");
                break;
            }
        }
        if (pg.size())
        {
            printf("1\n");
        }
    }

    return 0;
}