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