B - 同一円周上 AtCoder Regular Contest 047

問題概略
座標平面上にN個の点がある。それらとマンハッタン距離が等しい点Pを一つ求めよ。

制約
1<=N<=10^5

x,y

<= 10^9

解法
ある地点からマンハッタン距離が等しい点の集合はひし形になるため、45度回転させると正方形になる。
よって、与えられた点に回転行列(1 , -1) (45度) を掛けると(x,y) -> (x-y , x+y)になる。
.......................................................(1, 1)
任意の点に対してこの回転を行った時、それらを正方形の外周上に持つ原点があり、それを回転前に戻したものが答えである。
回転後のx,y をa,bとすると、max(aの最大の差とbの最大の差)+1の長さの辺を持つ正方形が作れる。
原点の座標は一辺を2rとして、完成後の正方形の(右端-r==左端+r , 上端-r ==下端+r)となる。
この時完成後の地点の右端,左端の内、少なくともどちらか片方が現在あり、高さについても同じことが言える。
つまり、原点(回転後)は(amin + r , bmin + r) , (amin +r , bmax -r ), (amax-r, bmin +r),(amax-r, bmax-r)のどれかである。
それぞれの場合について原点候補を回転前に戻してやり、マンハッタン距離が等しいか試せば解ける。
x,yを足したり割ったりすると回転前の座標が得られる。

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        x = nlah(N, 2);
        y = nlah(N, 2);
        a = new long[N];
        b = new long[N];
        for (int i = 0; i < N; i++) {
            a[i] = x[i] - y[i];
            b[i] = x[i] + y[i];
        }
        long amax = max(a);
        long amin = min(a);
        long bmax = max(b);
        long bmin = min(b);
        long r = (max(amax - amin, bmax - bmin) + 1) / 2;
        check(amin + r, bmin + r);
        check(amin + r, bmax - r);
        check(amax - r, bmin + r);
        check(amax - r, bmax - r);
    }

    public static void check(long rx, long ry) {
        long ox = (rx + ry) / 2;
        long oy = (rx - ry) / -2;
        long dis = Math.abs(x[0] - ox) + Math.abs(y[0] - oy);
        for (int i = 0; i < N; i++) {
            if (Math.abs(x[i] - ox) + Math.abs(y[i] - oy) != dis) return;
        }
        System.out.println(ox + " " + oy);
        System.exit(0);
    }