比赛 ZLXOI2015Day2 评测结果 AAAAAAAAAA
题目名称 妹妹的饼干 最终得分 100
用户昵称 ppfish 运行时间 0.003 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2015-10-30 20:01:35
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

template<class T>inline void Read(T &x)
{
    int f = 1;
    char t = getchar();
    while (t < '0' || t > '9') {
        if (t == '-') f = -1;
        t = getchar();
    }
    x = 0;
    while (t >= '0' && t <= '9') {
        x = x * 10 + t - '0';
        t = getchar();
    }
    x *= f;
}

const int maxn = 1025;

struct point { int x, y; };

int n;

point instate[maxn];
long long int_point;
long long area;

int gcd(int x, int y)
{
    if (y == 0) return x;
    else return gcd(y, x % y);
}

long long cross(int x1, int y1, int x2, int y2)
{
    return 1ll * x1 * y2 - 1ll * x2 * y1;
}

void input()
{
    Read(n);
    for (register int i = 1; i <= n; i++) Read(instate[i].x), Read(instate[i].y);
    instate[n + 1] = instate[1];
}

void solve()
{
    for (register int i = 1; i <= n; i++) {
        area += cross(instate[i].x, instate[i].y, instate[i + 1].x, instate[i + 1].y);
    }
    area = abs(area);
    for (register int i = 1; i <= n; i++) {
        int_point += 1ll * gcd(abs(instate[i + 1].x - instate[i].x), abs(instate[i + 1].y - instate[i].y));
    }
    cout << (area - int_point + 2) / 2 << endl;
}

int main()
{
    freopen("sistercookies.in", "r", stdin);
    freopen("sistercookies.out", "w", stdout);

    input();
    solve();
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}