Posted on 2009-10-02 03:01
Uriel 阅读(192)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
计算几何
求顶点为整数的任意多边形内部整点数(Pick定理)，边上整点数(GCD)，面积(叉积)
第一次知道Pick定理。。
注意。。叉积求出面积可能是负数，需要处理下
/**//*Problem: 1265 User: Uriel
Memory: 172K Time: 16MS
Language: C++ Result: Accepted*/
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define MAXN 110
#define ABS(x) (x<0?-x:x)
struct point
{
int x,y;
};
point P[MAXN],T;
int t,n,i,EPoint,IPoint,Asum;
int cross_product(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
int GCD(int x,int y)
{
if(y==0)return x;
else
return GCD(y,x%y);
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
scanf("%d",&n);
Asum=0;
EPoint=0;
P[0].x=0;
P[0].y=0;
for(int j=1;j<=n;j++)
{
scanf("%d %d",&T.x,&T.y);
P[j].x=P[j-1].x+T.x;
P[j].y=P[j-1].y+T.y;
EPoint+=GCD(ABS(T.x),ABS(T.y));
Asum+=cross_product(P[j-1],P[j]);
}
if(Asum<0)
{
Asum=-Asum;
}
IPoint=Asum/2+1-EPoint/2;
printf("Scenario #%d:\n%d %d %.1f\n\n",i,IPoint,EPoint,((double)Asum)/2);
}
// system("PAUSE");
return 0;
}