题目链接

题目大意:

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

(数据是按 $\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;
}
分类: 文章

Remmina

No puzzle that couldn't be solved.

发表评论

电子邮件地址不会被公开。 必填项已用*标注