这道题目用了蛮多结论的，要求格子面上多边形的边上点数，内部点数和占的面积，用到的结论：
1.以格子点为顶点的线段，覆盖的点的个数为GCD(dx,dy)，其中，dxdy分别为线段横向占的点数和纵向占的点数。如果dx或dy为0，则覆盖的点数为dy或dx。
2.Pick公式：平面上以格子点为顶点的简单多边形，如果边上的点数为on，内部的点数为in，则它的面积为A=on/2+in-1。（http://episte.math.ntu.edu.tw/articles/sm/sm_25_10_1/index.html有证明和推导）
3.任意一个多边形的面积等于按顺序求相邻两个点与原点组成的向量的叉积之和（黑书上有说明）
下面是我的实现代码：
#include <iostream>
using namespace std;
int Gcd( int a, int b ){ //a, b为两个输入的数，返回最大公约数
while( b!= 0 ){
int r= b;
b= a % b;
a= r;
}
return a;
}
int main(){
int i, k, t, n, x[101], y[101], dx, dy, on, in, area;
scanf("%d",&t);
for( k= 1; k<= t; k++ ){
scanf("%d",&n);
for( i= 1, on=area=x[0]=y[0]= 0; i<= n; i++ ){
scanf("%d%d",&dx,&dy);
x[i]= dx+ x[i-1];
y[i]= dy+ y[i-1];
on+= Gcd(abs(dx),abs(dy));
area+= x[i-1]*y[i]-x[i]*y[i-1];
}
in= ( area- on+ 2 )/ 2;
printf("Scenario #%d:\n%d %d %.1lf\n\n",k,in,on,area/2.0);
}
return 0;
}
posted on 2009-06-26 18:26
古月残辉 阅读(792)
评论(1) 编辑 收藏 引用 所属分类:
计算几何