mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 047 B - 同一円周上

解法

ある点からのマンハッタン距離が等しい頂点というのは, こんな感じ(◇)の形をしています。

これでは考えにくいので, 45 度回転させるイメージで, 座標 (x, y) を (x+y, x-y) に変換します。

すると, ある点からのマンハッタン距離が等しい頂点は, 変換した座標系では x 軸, y 軸に平行な辺を持つ正方形の上にあることがわかります。
正方形の 1 辺の長さは max(x 座標の最大値(xmax)と最小値(xmin)の差, y 座標の最大値(ymax)と最小値(ymin)の差) で与えることができ, この 1 辺の長さ D を用いると, 正方形の中心の座標は, x 座標は xmin+D/2, xmax-D/2 のいずれか, また y 座標は ymin+D/2, ymax-D/2 のいずれか, と書けるので, これらのうち条件に合うのを探せば良いです。

const int MAXN = 100010;
const ll INF = 1ll<<55;
ll X[MAXN], Y[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<ll> xm(2), ym(2);
    xm[0] = INF, xm[1] = -INF, ym[0] = INF, ym[1] = -INF;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
        ll x = X[i]+Y[i];
        ll y = X[i]-Y[i];
        xm[0] = min(x, xm[0]);
        xm[1] = max(x, xm[1]);
        ym[0] = min(y, ym[0]);
        ym[1] = max(y, ym[1]);
    }
    ll D = max(xm[1]-xm[0], ym[1]-ym[0])/2;
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
        ll x = xm[i]+D*(i==0?1:-1);
        ll y = ym[j]+D*(j==0?1:-1);
        ll ax = (x+y)/2, ay = (x-y)/2;
        ll d = -1;
        bool ng = false;
        for (int k = 0; k < N; k++) {
            ll D = abs(ax-X[k])+abs(ay-Y[k]);
            if (d != -1 && d != D) ng = true;
            d = D;
        }
        if (!ng) {
            cout << ax << " " << ay << endl;
            return 0;
        }
    }
    assert(false);
    return 0;
}