aoj 0524 - Searching Constellation

問題

問題概要

まず星座の座標のみが与えられる。次にゴミデータも含んだ星座の座標が与えられる。座標は相対的なもので、星と星の位置関係は変わらないが、1度目と2度目で与えられる絶対座標は異なる。どのように平行移動すれば絶対座標が一致するから求める問題。

解法

星座を構成する星たち相対座標は変化しない。ゴミデータを見分けなければならないので、まず1つ支点をきめる。今回は、星座のみの座標が与えれるときのクエリの一番初めの座標を支点とした。その点から、ほかのすべての星に対するベクトル成分を求めておく（v)。次に、ゴミデータを含む星の座標のなかから全探索を用いて、支点と一致する星を見つける。具体的な方法は、ゴミデータの中から支点を仮定して、その点からほかの星（n個（自分自身の星も含む））に対するベクトル成分を求める。その成分をvと比べてm個一致すれば、仮定した点が求める支点だったことがわかる。あとは平行移動を計算して出力するだけ。 オーダーはО(n²*m)なので間に合う。

ミス

特にない。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define fi first
#define se second

int main(void){
    while(1){
        int m; scanf("%d", &m);
        if(m == 0) break;
        vector<pair<int, int> > seiza(m);
        rep(i, m) scanf("%d %d", &seiza[i].fi, &seiza[i].se);

        //星座の支点からのベクトルを計算
        vector<pair<int, int> > v(m);//fi x座標 se y座標
        v[0].fi = 0, v[0].se = 0;//支点から支点へのベクトル
        //支点（一番初めに与えられた星座の座標）からすべてのほかの星座の座標へのベクトルを求める
        reps(i, 1, m){
            v[i].fi = seiza[i].fi - seiza[0].fi;
            v[i].se = seiza[i].se - seiza[0].se;
        }

        int n; scanf("%d", &n);
        vector<pair<int, int> > hosizora(n);//星空の点を入れる配列
        rep(i, n) scanf("%d %d", &hosizora[i].fi, &hosizora[i].se);
    
        int nowx, nowy;
        int cnt = 0;
        //上で決めた支点に対応するベクトルを全探索で探す
        rep(i, n){
            nowx = hosizora[i].fi;
            nowy = hosizora[i].se;
            rep(j, n){
                int vx = hosizora[j].fi - nowx;
                int vy = hosizora[j].se - nowy;
                rep(k, m){
                    if(vx == v[k].fi && vy == v[k].se){
                        cnt++;
                        break;
                    }
                }
            }
            //cnt==mになれば、mこのベクトル成分をすべて持つことになるので、今調べている支点が一致する支点
            if(cnt == m) break;
            cnt = 0;
        }
        printf("%d %d\n", nowx - seiza[0].fi, nowy - seiza[0].se);
    }
    return 0;
}