比赛 ZLXOI2015Day2 评测结果 AAAAAAAAAA
题目名称 妹妹的饼干 最终得分 100
用户昵称 dashgua 运行时间 0.003 s
代码语言 C++ 内存使用 0.39 MiB
提交时间 2015-10-30 19:58:04
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iostream>
#include <algorithm>

template<class Num>void read(Num &x)
{
	char c; int flag = 1;
    while((c = getchar()) < '0' || c > '9')
		if(c == '-') flag *= -1;
	x = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
		x = (x<<3) + (x<<1) + (c-'0');
	x *= flag;
	return;
}
template<class Num>void write(Num x)
{
	if(!x) {putchar('0');return;}
	if(x < 0) putchar('-'), x = -x;
	static char s[20];int sl = 0;
	while(x) s[sl++] = x%10 + '0',x /= 10;
    while(sl) putchar(s[--sl]);
}
const int maxn = 1e4;
typedef std::pair<int,int> Node;
#define X first 
#define Y second 

int N;
Node pos[maxn];
long long S, cnt;

long long cross(Node A, Node B)
{
	return (long long)A.X * B.Y - (long long)A.Y * B.X;
}
int gcd(int a,int b)
{
	return b == 0 ? a : gcd(b, a % b);
}
int count(Node A, Node B)
{
	return gcd(abs(A.X - B.X), abs(A.Y - B.Y));
}
void init()
{
	int x, y;
	
	read(N);
	
	for(int i = 1; i <= N; i++)
	{
		read(x), read(y);
		pos[i] = std::make_pair(x, y);
	}
}
void solve()
{
	if(N < 3)
	{
		putchar('0');
		return;
	}
	
	for(int i = 1; i < N; i++)
	{
		S += cross(pos[i], pos[i + 1]);
		cnt += count(pos[i], pos[i + 1]);
	}
	S += cross(pos[N], pos[1]);
	cnt += count(pos[N], pos[1]);
	
	write(((llabs(S) + 2) - cnt) >> 1);
}
int main()
{
	freopen("sistercookies.in","r",stdin);
	freopen("sistercookies.out","w",stdout);
	
	init();
	
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}