poj1265皮克定律

poj1265皮克定理

给出每次所走的距离dx,dy;   求多边形内部点的个数、边上点的个数、面积.

 

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
struct point
{
   int x,y;
};
int gcd(int m,int n)
{
	if(n==0) return m;
	return gcd(n,m%n);
}

int bian(point A,point B)//算出点A和点B组成的线段上的点
{
	return gcd(abs(A.x-B.x),abs(A.y-B.y));	
}

int f(point a[],int n)//求n边形的面积
{
	int i,ans=0;
	a[n]=a[0];
	for(i=0;i<n;i++)
	ans+=(a[i].x*a[i+1].y-a[i].y*a[i+1].x);
	if(ans<0) ans=-ans;
	return ans;
}


int main()
{  int s,ans,t,n,i,j=0;
   point a[105];
   cin>>t;
   while(j<t)
   { cin>>n;
     for(i=0;i<n;i++)
      {cin>>a[i].x>>a[i].y;
       if(i>0) {a[i].x+=a[i-1].x; a[i].y+=a[i-1].y;}
      }
      for(s=i=0;i<n;i++)
      { if(i==n-1) s+=bian(a[i],a[0]);
      else
      	s+=bian(a[i],a[i+1]);
      }
  	    
  	    ans=f(a,n);
  	    cout<<"Scenario #"<<++j<<":"<<endl<<(ans-s)/2+1<<" "<<s<<" "<<fixed<<setprecision(1)<<ans/2.0<<endl<<endl;
   }
	return 0;
}