Manhattan Distances [CSAcademy #51 C]

https://csacademy.com/contest/round-51/task/manhattan-distances/

概要

T(≦10^4)個のクエリが与えられる。
3つの頂点のマンハッタン距離だけ与えられるので、頂点を復元せよ。
もしありえないなら"-1"

解法

証明できないが通ったので紹介する。

マンハッタン距離を小さい順にv[0],v[1],v[2]とする。
ここで(0,0),(v[2],0)とすると、後もう一つの点のx座標は[0,v[2]]のどれかになる。
後もう1つの点を(a,b)とおくと、その点と(0,0)とのマンハッタン距離はa+b,(v[2],0)とのマンハッタン距離はv[2]-a+bとなる。
この2つの距離を足すとv[0]+v[1]となるはずなので、v[0]+v[1]=(a+b)+(v[2]-a+b)=v[2]+2*bとなる
よってb = (v[0] + v[1] - v[2]) / 2となる。
bは0以上の整数であるため、それをチェックして満たさないなら"-1"
満たすなら、a = v[0] - bとして答える。

void solve() {
    vector<int> v;
    rep(i, 0, 3) {
        int x; cin >> x; v.push_back(x);
    }
    sort(v.begin(), v.end());

    int b = (v[0] + v[1] - v[2]);
    if (b % 2 == 1 || b < 0) {
        printf("-1\n");
        return;
    }

    printf("0 0 ");
    printf("%d 0 ", v[2]);
    printf("%d %d\n", v[0] - b / 2, b / 2);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}