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