036 - Max Manhattan Distance（★5）
キーワード
解説
45 度回転を用いる.
全ての点について, 距離が最大となる点は が最大か最小の点, が最大か最小の点の 4 通り. 先に を計算しておく.
提出コード
type Position struct {
X int
Y int
}
func abs(a int) int {
if a < 0 {
return -a
}
return a
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}
func main() {
var n, Q int
scanIntVariables(&n, &Q)
poss := make([]Position, n)
for i := 0; i < n; i++ {
var x, y int
scanIntVariables(&x, &y)
poss[i] = Position{x - y, x + y}
}
minX := math.MaxInt
minY := math.MaxInt
maxX := math.MinInt
maxY := math.MinInt
for i := 0; i < n; i++ {
x := poss[i].X
y := poss[i].Y
if x < minX {
minX = x
}
if y < minY {
minY = y
}
if x > maxX {
maxX = x
}
if y > maxY {
maxY = y
}
}
for i := 0; i < Q; i++ {
q := readInt()
q--
x := poss[q].X
y := poss[q].Y
ans := max(abs(x-minX), abs(x-maxX))
ans = max(ans, abs(y-minY))
ans = max(ans, abs(y-maxY))
writeLine(ans)
}
}