学习了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 阅读(238)
评论(0) 编辑 收藏 引用 所属分类:
POJ