The Test Case

a.c (text/plain), 819 bytes, created by Luis Fernando Schultz Xavier da Silveira on 2009-07-02 17:09:07 UTC

/*
 * Area
 * 	source     = ACM ICPC 2001 - Northwestern Europe
 * 	difficulty = medium
 * 	keywords   = geometry number-theory
 */

#include <stdio.h>

static int gcd(int a, int b) {
	int r;
	if (a < 0)
		a = -a;
	if (b < 0)
		b = -b;
	while (b != 0) {
		r = a%b;
		a = b;
		b = r;
	}
	return a;
}

int main(void) {
	int tc, cs;
	int x0, y0, x1, y1, dx, dy;
	int n, i;
	int l;
	int area;

	scanf("%d", &tc);
	for (cs = 0; cs != tc; ++cs) {
		scanf("%d", &n);

		x0 = 0; y0 = 0;
		l = 0;
		area = 0;
		for (i = 0; i != n; ++i) {
			scanf("%d%d", &dx, &dy);
			l+= gcd(dx, dy);
			x1 = x0 + dx;
			y1 = y0 + dy;
			area+= x0*y1 - x1*y0;
			x0 = x1; y0 = y1;
		}
		if (area < 0)
			area = -area;

		printf("Scenario #%d:\n", cs+1);
		printf("%d %d %d.%d\n\n", (area+2-l)/2, l, area/2, area&1 ? 5 : 0);
	}

	return 0;
}