[poj 1265]Area[Pick定理][三角剖分]

题意:

给出机器人移动的向量, 计算包围区域的内部整点, 边上整点, 面积.

思路:

面积是用三角剖分, 边上整点与GCD有关, 内部整点套用Pick定理.

S = I + E / 2 - 1

I 为内整点数, E为边界整点数, S为面积.

Separate the three numbers by two single blanks.....好吧, 理解成中间空两格PE一次> <

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int MAXN = 105;

int n;

int GCD(int a, int b)

{

    return !b?a:GCD(b,a%b);

}

struct point

{

    int x,y;

}p[MAXN];

int det(int i, int j)

{

    return p[i].x*p[j].y - p[j].x*p[i].y;

}

double CalS()

{

    double ret = 0;

    for(int i=0;i<n;i++)

    {

        ret += det(i, i+1);

    }

    return fabs(ret/2.0);

}

int CalE()

{

    int ans = n;

    for(int i=0;i<n;i++)

    {

        int dx = (int)abs((double)(p[i].x - p[i+1].x));

        int dy = (int)abs((double)(p[i].y - p[i+1].y));

        if(!dx)

        {

            if(!dy) continue;

            ans += dy - 1;

            continue;

        }

        if(!dx)

        {

            ans += dx - 1;

            continue;

        }

        ans += GCD(dx, dy) - 1;

    }

    return ans;

}

int main()

{

    int T;

    scanf("%d",&T);

    for(int k=1;k<=T;k++)

    {

        scanf("%d",&n);

        p[0].x = p[0].y = 0;

        for(int i=1;i<=n;i++)

        {

            scanf("%d %d",&p[i].x,&p[i].y);

            p[i].x += p[i-1].x, p[i].y += p[i-1].y;

        }

        double S = CalS();

        int E = CalE();

        printf("Scenario #%d:\n%d %d %.1lf\n\n",k,(int)(S+1.0-E/2.0),E,S);

    }

}