ARC047 B問題：同一円周上

問題. 同一円周上

平面上に 個の格子点がある．マンハッタン距離でこれらの格子点からの距離が等しくなる格子点を求めよ．

制約： ，　

解法．1次変換

番目の格子点 を に1次変換する．この1次変換は各点に対して，原点を中心に時計回りに 回転して，原点を中心に 倍に拡大したあとに， 軸に関して折り返しをした変換である． の1次変換を行列で表現すると，
$$
\begin{pmatrix}
1 & 0 \\\
0 & -1
\end{pmatrix}
\begin{pmatrix}
\sqrt 2 & 0 \\\
0 & \sqrt 2
\end{pmatrix}
\begin{pmatrix}
\cos \frac{\pi}{4} & \sin \frac{\pi}{4} \\\
-\sin \frac{\pi}{4} & \cos \frac{\pi}{4}
\end{pmatrix}
\begin{pmatrix}
x_i \\\
y_i
\end{pmatrix}
$$
となる．
マンハッタン距離上で格子点 から等しい距離にある格子点全体は菱形をしているが，上の1次変換を行うと等しい距離にある格子点全体は の変換後の点を中心とした正方形をしている．またこの1次変換は格子点を格子点に写す全単射となる．ただし，この1次変換は 等長写像 ではないことに注意が必要である（∵ 倍に拡大）．下の図では，丸から同じ色の正方形への1次変換を表している．丸は中心座標からマンハッタン距離で4となる格子点である．
　　　

与えられた格子点全体 に対して1次変換を行った後の格子点全体 について考える． から等しい距離にある点 というのは，上で考察したとおり，ある長さ に対して を中心とした1辺の長さが の正方形全体の交点となる．1次元で考えると正方形は区間となり， 個の区間の端点が1点で交差する場合というのは座標値が最小の点と最大の点の区間が交差する初めての場所となる．あとはこの候補となる点を全探索すれば答えが求まる．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

ll dist(ll x1, ll y1, ll x2, ll y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

void Solve() {
    int n;
    cin >> n;

    vector<ll> x(n), y(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];

    array<ll, 2> x_mM = {LLONG_MAX, LLONG_MIN};
    array<ll, 2> y_mM = {LLONG_MAX, LLONG_MIN};
    for (int i = 0; i < n; ++i) {
        // 座標変換後の各座標値の最小値と最大値を求める
        // (x, y) -> (x + y, x - y)
        x_mM[0] = min(x_mM[0], x[i] + y[i]);
        x_mM[1] = max(x_mM[1], x[i] + y[i]);
        y_mM[0] = min(y_mM[0], x[i] - y[i]);
        y_mM[1]= max(y_mM[1], x[i] - y[i]);
    }

    const ll len = max(x_mM[1] - x_mM[0], y_mM[1] - y_mM[0]) / 2;
    ll px = 0, py = 0;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            ll tx = x_mM[i] + (i == 0 ? 1 : -1) * len;
            ll ty = y_mM[j] + (j == 0 ? 1 : -1) * len;

            if ((tx + ty) % 2 != 0 || (tx - ty) % 2 != 0) continue;

            bool valid = true;
            px = (tx + ty) / 2; py = (tx - ty) / 2;
            for (int k = 0; k < n; ++k) {
                if (dist(x[0], y[0], px, py) != dist(x[k], y[k], px, py)) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                cout << px << " " << py << '\n';
                return ;
            }
        }
    }
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    // cout << setprecision(8) << setiosflags(ios::fixed);

    Solve();

    return 0;
}

他の人のブログで45°回転と書いていたので一瞬迷った．