問題概要

座標平面上に $M$ 個の星を表す点 $1, 2, \dots, M$ が与えられる（星座を成している）。また、それとは別に座標平面上に $N$ 個の点 $M+1, M+2, \dots, M+N$ が与えられる。

点 $1, 2, \dots, M$ を一斉にある量だけ平行移動すると、それらすべてが、上に述べた $N$ 個の点のどれかに重なるという。また、そのような移動量は一意に定まることが保証されるという。

その移動量を求めよ。

制約

$1 \le M \le 200$
$1 \le N \le 1000$
$N+M$ 個の点の $x$ 座標と $y$ 座標はすべて $0$ 以上 $10^{6}$ 以下の整数

考えたこと

まずパッと思いつく方法は、 $N + M$ 個の点が存在し得るような座標値の範囲内で、平行移動量をすべて調べるという方法だろう。だが、平行移動量として考えられるのは

$x$ 軸方向： $-10^{6}$ 以上 $10^{6}$ 以下
$y$ 軸方向： $-10^{6}$ 以上 $10^{6}$ 以下

ということで、全部で $(2 \times 10^{6})^{2} = 4 \times 10^{12}$ 通りありうる。これは到底調べきれない。

そこで、「もし適切に平行移動したならば、星 $1$ は $N$ 個の点のいずれかに重なっている」ことに着目しよう。つまり、平行移動量は以下の $N$ 通りのみを調べれば十分なのだ。

星 $1$ が星 $M+1$ に重なるように平行移動する場合
星 $1$ が星 $M+2$ に重なるように平行移動する場合
...
星 $1$ が星 $M+N$ に重なるように平行移動する場合

$N$ 通りを調べるだけならば、十分に現実的だと考えられる。次に、平行移動量 $dx, dy$ を決めたときに、その平行移動量 $dx, dy$ が適するかどうかを判定する方法を考える。

平行移動量 $dx, dy$ が適するかの判定

$M$ 個の星 $1, 2, \dots, M$ に対して、 $dx, dy$ だけ平行移動して得られる座標が、 $N$ 個の星 $M+1, M+2, \dots, M+N$ のいずれかに一致するかを調べれば良い。

ここで、 $N$ 個の星の座標をあらかじめ集合型などに格納しておくとよい（C++ であれば set 型）。C++ の set 型を用いた場合、平行移動して得られる座標が、 $N$ 個の星の座標のいずれかに一致するかを $O(\log N)$ の計算量で判定できる。

よって、 $M$ 個の星全てについて判定するのに要する計算量は $O(M \log N)$ となる。

まとめ

まとめると、次の解法で解ける。

星 $1$ が星 $M+1, M+2, \dots, M+N$ に重なるように平行移動する $N$ 通りの場合を調べていく（ $N$ 通り）
各平行移動量について、星 $1, 2, \dots, M$ を平行移動して得られる座標が、星 $M+1, M+2, \dots, M+N$ のいずれかに一致するかを調べる（計算量 $O(M \log N)$ ）

全体の計算量は $O(MN \log N)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;

int main() {
    int M, N;
    cin >> M;
    vector<int> sx(M), sy(M);
    for (int i = 0; i < M; i++) cin >> sx[i] >> sy[i];
    cin >> N;
    vector<int> tx(N), ty(N);
    for (int i = 0; i < N; i++) cin >> tx[i] >> ty[i];

    // N 個の星の位置情報を set に入れておく
    set<pint> stars;
    for (int i = 0; i < N; i++) stars.insert(pint(tx[i], ty[i]));

    // 星座の 0 番目の星が、写真の i 番目の星と重なるかを check する
    int resx, resy;
    for (int i = 0; i < N; i++) {
        // dx, dy: 平行移動量
        int dx = tx[i] - sx[0], dy = ty[i] - sy[0];

        // 星座の j 番目の星を dx, dy だけ移動した位置に、星があるかを check する
        bool ok = true;
        for (int j = 0; j < M; j++) {
            if (!stars.count(pint(sx[j] + dx, sy[j] + dy))) ok = false;
        }
        if (ok) resx = dx, resy = dy;
    }
    cout << resx << " " << resy << endl;
}