マンハッタン距離の中間点を求めるC++コードの解説

2つの点 a = (x1, y1) と b = (x2, y2) が与えられたとき、2点間のマンハッタン距離は次のように定義されます。

dist(a, b) = |x1 − x2| + |y1 − y2|

ここで、点 a の座標を (0, 0)、点 b の座標を (x, y) とします。このとき、以下の2つの条件を同時に満たす点 c を求める必要があります。
・dist(a, c) = dist(a, b) ÷ 2
・dist(b, c) = dist(a, b) ÷ 2

もし条件を満たす点が存在しない場合は、「-1 -1」を出力します。

例として、入力が x = 13、y = 7 の場合、出力は「6 4」となります。

解法のアプローチ

この問題の鍵となるのは、x と y の偶奇（パリティ）です。点 c が a と b の両方から等しい距離（全体の距離の半分）に位置するためには、c は事実上「マンハッタン距離における中間点」でなければなりません。座標は整数である必要があるため、x と y の偶奇によって、答えが存在するかどうか、またどのような座標になるかが決まります。

アルゴリズムの手順

以下の手順に従って問題を解きます。

x を 2 で割った余りが 0、かつ y を 2 で割った余りが 0 の場合：
    print(x / 2, y / 2)
そうでなく、(x + y) を 2 で割った余りが 1 の場合：
    print(-1, -1)
それ以外の場合：
    print(x / 2, (y + 1) / 2)

なぜこの手順でうまくいくのか

• x も y も偶数の場合： 点 (x/2, y/2) は原点からも点 (x, y) からも同じ距離 (x+y)/2 に位置するため、条件を満たします。
• x + y が奇数の場合： マンハッタン距離 dist(a, b) = x + y が奇数になるため、その半分は整数になりません。整数座標の点では条件を満たせないため、「-1 -1」を出力します。
• x も y も奇数の場合： 一方の座標を切り捨て（x/2）、もう一方を切り上げ（(y+1)/2）することで、原点からの距離と点 (x, y) からの距離が一致します。

C++による実装例

実際の実装を見て、理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 100
void solve(int x, int y) {
    if(x % 2 == 0 && y % 2 == 0)
        cout<< x / 2 <<' '<< y / 2 <<endl;
    else if((x + y) % 2 == 1)
        cout<< -1 <<' '<< -1 <<endl;
    else
        cout<< x / 2 <<' '<< (y + 1) / 2 << endl;
}
int main() {
    int x = 13, y = 7 ;
    solve(x, y);
    return 0;
}

入力

13, 7

出力

6 4

まとめ

この問題は、マンハッタン距離の性質と座標の偶奇に着目することで、O(1) の計算量で解くことができます。x と y が両方とも偶数なら (x/2, y/2)、両方とも奇数なら (x/2, (y+1)/2)、偶奇が混在する場合は解が存在しない、というシンプルな判定だけで十分です。