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

using namespace std;

typedef long long LL;

const int maxn = 1030;

struct Point
{
	int x, y;
	Point operator - (const Point &a) const { return (Point){x - a.x, y - a.y}; }
}p[maxn];

inline LL cross(const Point &a, const Point &b)
{
	return a.x * b.y - a.y * b.x;
}

inline LL cross(const Point &a, const Point &b, const Point &c)
{
	return cross(b - a, c - a);
}

int n;

void input()
{
	scanf("%d", &n);
	for(int i = 0; i < n; ++i)
		scanf("%d%d", &p[i].x, &p[i].y);
}

//pick: S = a + b/2 - 1
//a = S - b/2 + 1

void solve()
{
	LL S = 0, b = 0;
	for(int i = 0; i+2 < n; ++i)
		S += cross(p[0], p[i+1], p[i+2]);
	S = abs(S);
	
	for(int i = 0; i < n; ++i)
	{
		Point q = p[(i+1)%n] - p[i];
		b += __gcd(abs(q.x), abs(q.y));
	}
	LL a = S - b + 2;
	cout << a / 2 << endl;
}

int main()
{
	freopen("sistercookies.in", "r", stdin);
	freopen("sistercookies.out", "w", stdout);
	
	input();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}