GCJ/2008/2/C/main.go

package main

import (
	"fmt"
)

func main() {
	var T, N int
	fmt.Scan(&T)
	for cid := 0; cid < T; cid++ {
		fmt.Scan(&N)
		// ********** This is the standard answer given by GCJ **********
		// Assume that minimum energy is E, for each (xi, yi, zi),
		// we have |x-xi| + |y-yi| + |z-zi| <= Epi, which is
		// xi + yi + zi - Epi <= x + y + z <= Epi + xi + yi + zi
		// xi - yi + zi - Epi <= x - y + z <= Epi + xi - yi + zi
		// xi + yi - zi - Epi <= x + y - z <= Epi + xi + yi - zi
		// yi + zi - xi - Epi <= y + z - x <= Epi - xi + yi + zi
		// so 0 <= Epi. What's more,
		// A - x <= y + z <= B - x, G + x <= y + z <= H + x,
		// x - D <= y - z <= x - C, E - x <= y - z <= F - x
		// if y and z is solvable, then [A-x, B-x] and [G+x, H+x] must
		// intersect, [x-D, x-C] and [E-x, F-x] must intersect.
		// For first two range, x in [(A-H)/2, (B-G)/2], for the second,
		// x in [(E+C)/2, (F+D)/2]. So we just have to test if the two
		// range intersects.
		// ???
		// **************************************************************
		// In fact, the position of mother ship should be in the cuboid
		// area between two of the ships. For ship A and ship B, we
		// have: |x-xa|+|y-ya|+|z-za| = paE, |x-xb|+|y-yb|+|z-zb| = pbE;
		// so dista + distb = (pa + pb)E, E = distab / (pa + pb)
		// max E = max (distab/(pa+pb))
		ships := make([][]int, N)
		for i := 0; i < N; i++ {
			ships[i] = make([]int, 4)
			fmt.Scan(&ships[i][0], &ships[i][1], &ships[i][2], &ships[i][3])
		}
		maxPower := 0.
		for i := 0; i < N; i++ {
			for j := 0; j < N; j++ {
				dist := abs(ships[i][0]-ships[j][0]) + abs(ships[i][1]-ships[j][1]) + abs(ships[i][2]-ships[j][2])
				powerSum := ships[i][3] + ships[j][3]
				power := float64(dist) / float64(powerSum)
				if maxPower < power {
					maxPower = power
				}
			}
		}
		fmt.Printf("Case #%d: %f\n", cid+1, maxPower)
	}
}