競プロ典型90問 036 コード 問題 \((u_i, v_i) = (x_i + y_i, x_i - y_i)\) と座標変換する. このとき, クエリの点を \((u, v)\) とすると, 最大のマンハッタン距離は \(max(\abs{u-u_i}, \abs{v-vi})\) となる. これは \((u_i, v_i)\) を \(u_i\) でソートしたものと \(v_i\) でソートしたものを別に持っておけばいい.