CS Academy Round 51 - Manhattan Distances
整数d1, d2, d3が与えられる。2次元格子点座標の3点であって、各点のマンハッタン距離がd1, d2, d3のいずれかになるような3点を構成せよ。できない場合は-1を出力せよ。
マンハッタン距離は距離と名付けてあるだけあって、距離公理を満たす。その為、三角不等式の成立条件が構成できる第一条件である。次に格子点座標にある場合、それらのマンハッタン距離はその三点を囲う最小の長方形の周囲の長さに等しくなる。(図を書いてみるとすぐわかる。そのため、d1＋d2＋d3が偶数であることも必要であり、かつ十分である。
そこで、単純な例として、長方形の一片が構成する3点のうちの2点でかつd1～d3の中で最大のもの(例えばd1とする)であり、その片方が原点であるようなものを考える。すると(0, 0), (0, d1) と座標が決まる。すると、残りの1点は((d2 + d3 - d1) / 2, (d2 + d1 - d3) / 2)などとなる。O(1)。
