這道題用到了一個我不知道的定理，Pick定理。意思是格子面上的多邊形的邊的點的個數(shù)on和內(nèi)部點的個數(shù)in的關(guān)系式Area = on / 2 + in - 1;
求Area可以用叉乘法。注意最后那個Area/=2.0。
Code：
/**//*TOJ 1011 Area
pick theory */
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int px[100],py[100];
int gcd(int a,int b)
{
int temp;
while(b!=0){
temp=b;
b=a%b;
a=temp;
}
return a;
}
int main(void)
{
int cas,dx,dy,on,in,i,j,n;
double area;
scanf("%d",&cas);
for(j=1;j<=cas;j++){
scanf("%d",&n);
px[0]=py[0]=dx=dy=area=on=0;
for(i=1;i<=n;i++){
scanf("%d%d",&dx,&dy);
on+=gcd(abs(dx),abs(dy));
px[i]=px[i-1]+dx;
py[i]=py[i-1]+dy;
area+=(px[i-1]*py[i]-px[i]*py[i-1]);
}
area=area/2.0;
in=area+1-on/2;
printf("Scenario #%d:\n%d %d %.1lf\n\n",j,in,on,area);
}
}