AOJ 0524 - Searching Constellation

問題 : Searching Constellation | Aizu Online Judge

JOI 2007 問題4

解法: 全探索

与えられる星の座標を一点ずつ星座の一つ目の座標であると仮定して矛盾(次の星が見つからない)が起きるまで繰り返す(dfs)。
矛盾なく最後の点まで辿り着けばそれが求める星座である。
あとは与えられた星座と求めた星座との相対的な座標を求めればよい。

#include<iostream>
#include<set>
using namespace std;
typedef pair<int,int> P;

set<P> data;
set<P>star;

bool dfs(set<P>::iterator d,set<P>::iterator s){
	if(d==data.end())return false;
	if(s==--star.end())return true;
	set<P>::iterator tmp=++s;
	--s;
	P now=P((*tmp).first-(*s).first,(*tmp).second-(*s).second);
	P next=P((*d).first+now.first,(*d).second+now.second);
	
	return dfs(data.find(next),++s);
}

int main(){
	int n;
	while(cin>>n && n){
		data.clear();
		star.clear();
		for(int i=0;i<n;i++){
			P a;
			cin>>a.first>>a.second;
			star.insert(a);
		}
		int m;
		cin>>m;
		for(int i=0;i<m;i++){
			P a;
			cin>>a.first>>a.second;
			data.insert(a);
		}
		P ans;
		for(set<P>::iterator itr=data.begin();itr!=data.end();itr++){
			if(dfs(itr,star.begin()))ans=P((*itr).first-(*star.begin()).first,(*itr).second-(*star.begin()).second);
		}
		
		cout<<ans.first<<" "<<ans.second<<endl;
	}
}

個人的にはゴツゴツした全探索といった印象。
なんとなく抵抗がある。

イテレータが乱雑で冗長なコードになってしまったのも一つ原因である気がする。