using namespace std;
struct node{
int x;
int y;
}point[105];
int gcd(int m, int n)
{
if (m == 0)
return n;
if (n == 0)
return m;
while ((m%n)!=0)
{
int tmp = m % n;
m = n;
n = tmp;
}
return n;
}
int findL(node a,node b){
int dx = abs(int(a.x - b.x));
int dy = abs(int(a.y - b.y));
if(dx == 0 && dy == 0) return 0;
if(dx == 0) return dy - 1;
if(dy == 0) return dx - 1;
return gcd(dx,dy) - 1;
}
double getarea(node a[],int n){
double area1 = 0,area2 = 0;
for(int i = 0;i < n;i++){
area1 = area1 + a[(i+1)%n].y * a[i].x;
area2 = area2 + a[(i+1)%n].y * a[(i+2)%n].x;
}
return fabs(area1 - area2)/2.0;
}
int main(){
int m,t;
int ans = 1;
scanf("%d",&t);
while(t--){
scanf("%d",&m);
point[0].x = point[0].y = 0;
int x,y;
for(int i = 1;i <= m;i++){
scanf("%d%d",&x,&y);
point[i].x = point[i-1].x + x;
point[i].y = point[i-1].y + y;
}
int N =0,L = 0;
double A = 0;
L = L + m + findL(point[0],point[m - 1]);
for(int i = 0;i < m - 1;i++)
L = L + findL(point[i],point[i+1]);
A = getarea(point,m);
N = (int)A - L/2 + 1;
printf("Scenario #%d:\n",ans);
printf("%d %d %.1lf\n\n",N,L,A);
ans++;
}
return 0;
}zoj1032解题报告
原文：http://www.cnblogs.com/wanghaoyue/p/4061634.html
