AOJ 0524: Searching Constellation

星座にある星(固定しておく)から写真にある星までのベクトルを考えれば、並行移動の仕方はn通り
あることが分かります。n通り全て試すためには、1通り試すのにO(m+n)やO(mlogn)程度で良いです。

辞書順にソートしておくことで、O(n^2+mn)で解くことができます。

計算量は変わりませんが、ソートされているので、枝刈りすることができます。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int m,n;

struct co{
	int x,y;
};

bool operator<(const co& a,const co&b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
}

int main(){
	while(scanf("%d",&m),m){
		vector<co> p(m);
		for(int i = 0; i < m; i++){
			int a,b;
			scanf("%d%d",&a,&b);
			p[i].x = a;p[i].y = b;
		}
		
		scanf("%d",&n);
		
		vector<co> q(n);
		for(int i = 0; i < n; i++){
			int a,b;
			scanf("%d%d",&a,&b);
			q[i].x = a;q[i].y = b;
		}
		
		sort(p.begin(),p.end());sort(q.begin(),q.end());
		
		for(int i = 0; i < n; i++){
			int dx = q[i].x-p[0].x, dy = q[i].y-p[0].y;
			int pp = 1,qp = i;
			while(qp < n && pp < m){
				while(qp < n && (p[pp].x+dx!=q[qp].x || p[pp].y+dy!=q[qp].y))qp++;//p[pp].x+dx < q[qp].x になった時点で止めると速くなる。
				pp++;
			}
			if(pp == m){
				printf("%d %d\n",dx,dy);
				break;
			}
		}
	}
	return 0;
}