比赛 ZLXOI2015Day2 评测结果 AAAAAAWWWW
题目名称 妹妹的饼干 最终得分 60
用户昵称 forever 运行时间 0.004 s
代码语言 C++ 内存使用 0.54 MiB
提交时间 2015-10-30 21:07:45
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int n;
LL ans=0,S=0,ins=0;
struct point{
	LL x;
	LL y;
	double ta;
	point(){ x=0;y=0;ta=0.0;}
	point operator -(const point &a){
		point b;
		b.x=x-a.x;b.y=y-a.y;
		return b;
	}
	LL operator ^(const point &a){
		LL cd;
		cd=x*a.y-y*a.x;
		return cd;
	}
}p[10002];
LL gcd(LL x,LL y){
	if(!x)return y;
	if(!y)return x;
	if(x>y)return gcd(x%y,y);
	return gcd(x,y%x);
}
point Abs(point a){
	if(a.x<0) a.x=-a.x;
	if(a.y<0) a.y=-a.y;
	return a;
}
LL sqr()
{
	LL mars=0;
	for(int i=1;i<=n;i++) mars+=p[i]^p[i+1];
	if(mars<0) mars=-mars;
	return mars;
}
LL onside()
{
	LL cnt=0;
	point v;
	for(int i=1;i<=n;i++){
		v=p[i+1]-p[i]; v=Abs(v);
		cnt+=gcd(v.x,v.y)-1;
	}
	cnt+=(LL)(n);
	return cnt;
}
void work(){
	S=sqr();
	ins=onside();
	ans=(S-ins)/2+1;
}
int main(){
	freopen("sistercookies.in","r",stdin);
	freopen("sistercookies.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y); p[n+1]=p[1];
	work();
	printf("%d",ans);
	return 0;
}