Volume 5 / 0524

情報オリンピック 2007予選 解答

Problem 0524 : Searching Constellation / 星座探し

星座のある点を基準点とおいて、基準点-その他の点間の距離を保存。（dis_m[0..m-1]）
与えられた星のおのおのの座標（pos_n[0..n-1]）について、↑の距離を足したところに星が存在するか調べる。
星座を構成する全ての星が存在するのならば、星座の基準点と探索の基準点に使った点の間の距離を出力。

#include <iostream>
#include <vector>

using namespace std;

struct POS {
	int x, y;
};

bool is_exist( vector<POS> src, int x, int y )
{
	for( int i=0; i<src.size(); i++ )
		if( src[i].x == x && src[i].y == y )
			return true;

	return false;
}

int main(void)
{
	int m, n, x, y, i, j;
	vector<POS> dis_m, pos_n;

	while( cin >> m, m!=0 ){
		dis_m.clear(); pos_n.clear();

		dis_m.resize(m);

		int x0, y0;
		cin >> x0 >> y0;
		for( i=1; i<m; i++ ){
			cin >> x >> y;
			dis_m[i].x = x-x0;
			dis_m[i].y = y-y0;
		}

		cin >> n;
		pos_n.resize(n);
		for( i=0; i<n; i++ )
			cin >> pos_n[i].x >> pos_n[i].y;

		for( i=0; i<n; i++ ){
			for( j=1; j<m; j++ )
				if( !is_exist( pos_n, pos_n[i].x+dis_m[j].x, pos_n[i].y+dis_m[j].y ) )
					break;

			if( j == m ){
				cout << pos_n[i].x-x0 << " " << pos_n[i].y-y0 << endl;
				break;
			}
		}
	}

	return 0;
}