比赛 |
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;
}