poj 3348 Cows

這個題用到2個計算幾何算法。求解凸包和簡單多邊形面積。凸包算法詳細解釋見算法導論。求解多邊形面積的思想是將多邊形分解為三角
形，一般是假設按順序取多邊形上面連續的2點與原點組合成一個三角形，依次下去用叉積求有向面積之和，最後取絕對值即可。注意，這些
點必須是在多邊形上逆時針或者順時針給出的，而求出凸包剛好給了這樣的一系列點。
   凸包代碼，其實先找出一個y坐標最小的點，再對剩下的所有點按極角排序。然後對排序後的點進行一個二維循環即可。二維循環的解釋是
當加入新的點進入凸包集合時候，如果與以前加入的點形成的偏轉方向不一致，那麼前面那些點都需要彈出集合。

   代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX_N (10000 + 10)

struct Point
{
    double x, y;
    bool operator <(const Point& p) const
    {
        return y < p.y || y == p.y && x < p.x;
    }
};

Point pts[MAX_N];
int nN;
Point ans[MAX_N];
int nM;

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 CrossCmp(const Point& a, const Point& b)
{
    double cs = Cross(pts[0], a, b);
    return cs > 0 || cs == 0 && a.x < b.x;
}

void Scan()
{
    nM = 0;
    sort(pts + 1, pts + nN, CrossCmp);//對所有點按極角排序,逆時針偏轉
   
    //第0-2個點，其實不會進入第二重循環的
    //從第3個點開始，就依次檢查與凸包中前面點形成的邊的偏轉方向
    //如果不是逆時針偏轉，則彈出該點
    for (int i = 0; i < nN; ++i)
    {
        while (nM >= 2 && Cross(ans[nM - 2], ans[nM - 1], pts[i]) <= 0)
        {
            nM--;
        } www.2cto.com
        ans[nM++] = pts[i];
    }
}

double GetArea()
{
    double fAns = 0.0;
    Point ori = {0.0, 0.0};
    for (int i = 0; i < nM; ++i)
    {
        fAns += Cross(ori, ans[i], ans[(i + 1) % nM]);
    }
    return fabs(fAns) * 0.5;
}

int main()
{
    while (scanf("%d", &nN) == 1)
    {
        for (int i = 0; i < nN; ++i)
        {
            scanf("%lf%lf", &pts[i].x, &pts[i].y);
            if (pts[i] < pts[0])
            {
                swap(pts[i], pts[0]);//pts[0]是y坐標最小的點
            }
        }
       
        Scan();//掃描出凸包
        double fArea = GetArea();
        printf("%d\n", (int)(fArea / 50));
    }
   
    return 0;
}