poj 1265 Area

此題用到了幾個知識，一個是求多邊形面積的公式。然後是，根據頂點都在整點上求多邊形邊界上的頂點數目的方法。最後一個是pick
定理。根據前面2個信息和pick定理算出在多邊形內部的整點的個數。
   求多邊形面積的方法還是叉積代表有向面積的原理，把原點看做另外的一個點去分割原來的多邊形為N個三角形，然後把它們的有向面
積加起來。
   判斷邊界上點的個數是根據Gcd（dx,dy)代表當前邊上整數點的個數的結論。這個結論的證明其實也比較簡單，假設dx = a，dy = b。
初始點是x0，y0，假設d = Gcd（a，b）。那麼邊上的點可以被表示為（x0 + k * (a / d)，y0 + k * （b / d))。為了使點是整數點，
k必須是整數，而且0<= k <=d，所以最多有d個這個的點。
   求多邊形內部點的個數用的是pick定理。面積 = 內部點 + 邊界點 / 2 - 1。
  
   代碼如下：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAX (100 + 10)

struct Point
{
    double x, y;
};
Point pts[MAX];

int nN;
const int IN = 1;
const int EAGE = 2;
const int OUT = 3;
const double fPre = 1e-8;

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);
}

double GetArea()
{
    double fArea = 0.0;
    Point ori = {0.0, 0.0};

    for (int i = 0; i < nN; ++i)
    {
        fArea += Cross(ori, pts[i], pts[(i + 1) % nN]);
    }
    return fabs(fArea) * 0.5;
}

int gcd(int nX, int nY)
{
    if (nX < 0)
    {
        nX = -nX;
    }
    if (nY < 0)
    {
        nY = -nY;
    }
    if (nX < nY)
    {
        swap(nX, nY);
    }
    while (nY)
    {
        int nT = nY;
        nY = nX % nY;
        nX = nT;
    }
    return nX;
}

int main()
{
    int nT;
    int nI, nE;
    double fArea;

    scanf("%d", &nT);
    int dx ,dy;
   
    for (int i = 1; i <= nT; ++i)
    {
        scanf("%d", &nN);
        nI = nE = 0;
        pts[0].x = pts[0].y = 0;
        for (int j = 1; j <= nN; ++j)
        {
            scanf("%d%d", &dx, &dy);
            pts[j].x = pts[j - 1].x + dx;
            pts[j].y = pts[j - 1].y + dy;
            nE += gcd(dx, dy);
        } www.2cto.com
        fArea = GetArea();
        nI = (fArea + 1) - nE / 2;
        printf("Scenario #%d:\n%d %d %.1f\n\n", i, nI, nE, fArea);
    }

    return 0;
}