1143.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1143 on 2006-01-04 at 15:16:16 */ 
#include <cstdio>
#include <cstdlib>

int gcd(int, int);

int main()
{
	int n, x, y;
	int t, T, i;
	
	scanf("%d", &T);
	for(t = 1; t <= T; t++) {
		scanf("%d", &n);
		x = y = 0;
		int A = 0, E = 0;
		for(i = 0; i < n; i++) {
			int dx, dy, d;
			scanf("%d %d", &dx, &dy);
			A += x * (y + dy) - y * (x + dx);
			x += dx, y += dy; dx = abs(dx); dy = abs(dy);
			if(dx*dy == 0) E += dx + dy;
			else {
				int r = 1;
				while((d = gcd(dx, dy)) != 1) dx /= d, dy /= d, r *= d;
				E += r;
			}
		}
		A = abs(A);
		int I = (A - E) / 2 + 1;
		printf("Scenario #%d:\n", t);
		printf("%d %d %.1lf\n\n", I, E, (double)A/2);
	}
	
	return 0;
}

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a%b);
}