/* * Area * source = ACM ICPC 2001 - Northwestern Europe * difficulty = medium * keywords = geometry number-theory */ #include 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; }