けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 予選 2008 D - 星座探し (AOJ 0524) (4Q, 難易度 5)

平行移動量の候補を絞る考え方を使う!

問題概要

座標平面上に  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;
}