比赛 |
ZLXOI2015Day2 |
评测结果 |
C |
题目名称 |
妹妹的饼干 |
最终得分 |
0 |
用户昵称 |
God-Nan |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2015-10-30 21:27:50 |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct data
{
double x,y;
}lz[1100];
bool cmp(data a,data b)
{
return a.x<b.x&&a.y>b.y;
}
double gcd(int a,int b);
int cool(int a,int b,int c);
double clear(double x1,double y1,double x2,double y2);
int main()
{
freopen("sistercookies.in","r",stdin);
freopen("sistercookies.out","w".stdout);
int n,i,p,k,ans=0;
double qq;
scanf("%d",&n);
for(i=1;i<=n;i++)
{scanf("%lf%lf",&lz[i].x,&lz[i].y);}
sort(lz,lz+n,cmp);
for(i=2;i<=n-1;i++)
ans+=cool(1,i,i+1);
printf("%d",ans);
return 0;
}
int cool(int a,int b,int c)
{
int tmp=0;
double a1,a2,a3=1,b1,b2,b3=1,c1,c2,c3=1,s,o=0;
a1=lz[a].x;a2=lz[a].y;b1=lz[b].x;b2=lz[b].y;c1=lz[c].x;c2=lz[c].y;
s=0.5*(a1*b2*c3+b1*c2*a3+c1*a2*b3-a3*b2*c1-b3*c2*a1-c3*a2*b1);
s=fabs(s);
o+=clear(a1,a2,b1,b2);
o+=clear(b1,b2,c1,c2);
o+=clear(a1,a2,c1,c2);
tmp=int(s-0.50000-o/2);
return tmp;
}
double clear(double x1,double y1,double x2,double y2)
{
double tmp=0;
if(x1==x2)
{tmp=fabs(y2-y1)-1;}
else if(y1==y2)
{tmp=fabs(x2-x1)-1;}
else
{
int X=x2-x1,Y=y2-y1;
X=fabs(X);Y=fabs(Y);
tmp=gcd(X,Y);
tmp--;
}
return tmp;
}
double gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}