學習了pick定理
給定頂點座標均是整點（或正方形格點）的簡單多邊形，皮克定理說明了其面積A和內部格點數目i、邊上格點數目b的關系：A = i + b/2 - 1。
#include<iostream>
#include<math.h>
using namespace std;
#define MAXN 500
struct point
{int x,y;};
point p[MAXN];
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
//計算多邊形面積,頂點按順時針或逆時針給出
double area_polygon(int n,point* p){
double s1=0,s2=0;
int i;
for (i=0;i<n;i++)
s1+=p[(i+1)%n].y*p[i].x,s2+=p[(i+1)%n].y*p[(i+2)%n].x;
return fabs(s1-s2)/2;
}
int main()
{
int tc,m,I,E,dx,dy,i,j,k;
scanf("%d",&tc);
for(k=1;k<=tc;k++)
{
scanf("%d",&m);
p[0].x=0;
p[0].y=0;
E=0;
for(i=1;i<=m;i++)
{
scanf("%d%d",&dx,&dy);
p[i].x=p[i-1].x+dx;
p[i].y=p[i-1].y+dy;
E+=gcd(abs(dx),abs(dy));
}
double area=area_polygon(m+1,p);
I=(2*area+2-E)/2;
printf("Scenario #%d:\n%d %d %.1lf\n\n",k,I,E,area);
}
return 0;
}
posted on 2009-10-06 17:58
wyiu 閱讀(246)
評論(0) 編輯 收藏 引用 所屬分類:
POJ