GCJ/2008/3/A/main.go

package main

import (
	"fmt"
)

func main() {
	var N, L int
	fmt.Scan(&N)
	for cid := 0; cid < N; cid++ {
		fmt.Scan(&L)
		const sideLen = 6000
		vert, hori := make([][]bool, sideLen), make([][]bool, sideLen+1)
		for i := range vert {
			vert[i] = make([]bool, sideLen+1)
		}
		for i := range hori {
			hori[i] = make([]bool, sideLen)
		}
		x, y := 3000, 3000
		detX, detY := 0, 1
		xMin, xMax, yMin, yMax := Pair{3000, 3000}, Pair{3000, 3000}, Pair{3000, 3000}, Pair{3000, 3000}
		// For detail explanation, please refer to https://code.google.com/codejam/contest/32002/dashboard#s=a&a=0
		for i := 0; i < L; i++ {
			var move string
			var repeat int
			fmt.Scan(&move, &repeat)
			for r := 0; r < repeat; r++ {
				for _, m := range move {
					switch m {
					case 'L':
						detX, detY = -detY, detX
					case 'R':
						detX, detY = detY, -detX
					case 'F':
						if detY == 0 { // Move towards x dir
							hori[y][(2*x+detX)/2] = true
						} else { // ... y dir
							vert[(2*y+detY)/2][x] = true
						}
						x, y = x+detX, y+detY
						if x < xMin._1 || (xMin._1 == x && y < xMin._2) {
							xMin._1, xMin._2 = x, y
						}
						if xMax._1 < x || (xMax._1 == x && xMax._2 < y) {
							xMax._1, xMax._2 = x, y
						}
						if y < yMin._2 || (yMin._2 == y && yMin._1 < x) {
							yMin._1, yMin._2 = x, y
						}
						if yMax._2 < y || (yMax._2 == y && x < yMax._1) {
							yMax._1, yMax._2 = x, y
						}
					}
				}
			}
		} // Construct the edge graph and the position of 4 key points
		//          v____           <-- yMax
		//        __|    |___v      <-- xMax
		//     __|           |
		//    |              |
		//    |____        __|
		//    ^    |     _|         <-- xMin
		//         |____|
		//              ^           <-- yMin
		polyArea := 0
		for y := yMin._2; y < yMax._2; y++ {
			cnt := 0
			for x := xMin._1; x <= xMax._1; x++ {
				if vert[y][x] {
					cnt++
				}
				if cnt%2 == 1 { // Cross vert edge odd times: innner, even: outter
					polyArea++
				}
			}
		}
		stairArea := 0
		for x, hei := xMax._1-1, xMax._2; yMax._1 <= x; x-- {
			for y := hei + 1; y <= yMax._2; y++ {
				if hori[y][x] {
					hei = y
				}
			}
			stairArea += yMax._2 - hei
		}
		for y, hei := yMax._2-1, yMax._1; xMin._2 <= y; y-- {
			for x := hei - 1; xMin._1 <= x; x-- {
				if vert[y][x] {
					hei = x
				}
			}
			stairArea += hei - xMin._1
		}
		for x, hei := xMin._1, xMin._2; x < yMin._1; x++ {
			for y := hei - 1; yMin._2 <= y; y-- {
				if hori[y][x] {
					hei = y
				}
			}
			stairArea += hei - yMin._2
		}
		for y, hei := yMin._2, yMin._1; y < xMax._2; y++ {
			for x := hei + 1; x <= xMax._1; x++ {
				if vert[y][x] {
					hei = x
				}
			}
			stairArea += xMax._1 - hei
		}
		squareArea := (xMax._1 - xMin._1) * (yMax._2 - yMin._2)
		fmt.Printf("Case #%d: %d\n", cid+1, squareArea-stairArea-polyArea)
	}
}