【题解】Area 皮克定理 POJ – 1265

题目链接

题目大意：

给一个整点多边形，求其面积、多边形上整点数目、多边形内整点数目

（数据是按 $\Delta x, \Delta y$给出的）

点数和 $|\Delta |$$\leq 100$

这题就是皮克定理的模板题啦！

皮克定理英文名：Pick’s theorem

定理内容：

对于一个整点多边形，设多边形内的整点数目为 $a$，多边形上的整点数目为 $b$，面积为 $s$，有：

$$2s = 2a + b – 2$$

多边形内的整点数目不是很好求，但是面积可以用叉积轻松求出，多边形上的点也可以用 $gcd$求出来，于是代入方程就能解出多边形内的整点数目啦~\(≧▽≦)/~

（值得注意的是制杖 POJ 中你用 G++交会莫名其妙 WA，而且这题每组数据之后要输出两个换行。。。）

代码：

#include <cstdio>
#include <cctype>

#define ABS(a) ((a) < 0 ? (-(a)) : (a))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int testcase, n;

int main(int argc, char const* argv[])
{
    IN(testcase);
    for (int C = 1; C <= testcase; C += 1)
    {
        IN(n);
        int size = 0, side = 0, in, x1 = 0, y1 = 0, x2, y2;
        for (int i = 1, x, y; i <= n; i += 1)
        {
            IN(x), IN(y);
            x2 = x1 + x, y2 = y1 + y;
            size += x1 * y2 - x2 * y1;
            side += gcd(ABS(x), ABS(y)), x1 = x2, y1 = y2;
        }
        in = (size - side + 2) >> 1;
        printf("Scenario #%d:\n%d %d %.1f\n", C, in, side, (double)0.5 * size);
    }
    return 0;
}