1265.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"math.h"
#include"stdio.h"
int x[110],y[110];
int main()
{int t,i,j,n,dx,dy,ys,k;
	double s;long a;
	cin>>t;
	for(k=1;k<=t;k++)
	{cin>>n;
	x[0]=0;y[0]=0;
	for(i=1;i<=n;i++)
	{cin>>dx>>dy;
	x[i]=x[i-1]+dx;
	y[i]=y[i-1]+dy;
	}
	s=0;
	for(i=2;i<=n;i++)
		s+=x[i]*y[i-1]-x[i-1]*y[i];
	s=fabs(s)/2;

	a=0;
	for(i=0;i<n;i++)
	{dx=x[i+1]-x[i];if(dx<0)dx=-dx;
	 dy=y[i+1]-y[i];if(dy<0)dy=-dy;
	 ys=dy;
	 if(ys<dx)ys=dx;
	 for(;ys>0;ys--)
	 if(dy%ys==0&&dx%ys==0)break;
	 a+=ys;
	}
		
	printf("Scenario #%d:\n%ld %ld %.1f\n\n",k,long(s-(a/2-1)),a,s);
	}

	return 0;
}