AOJ0524 Searching Constellation
あまり考えずに書いたので無駄なことしてる
#include <cstdio> #include <vector> #include <algorithm> #include <map> using namespace std; int m, n, tmp; pair<int,int> ans; bool comp(const pair<int,int> a, const pair<int,int> b){ return a.first > b.first; } int main(){ while(scanf("%d", &m)){ if(m == 0) break; vector<pair<int,int> > seiza, d, cst; map<pair<int,int>, int> star; for(int i = 0; i < m; i++){ int p, q; scanf("%d %d", &p, &q); seiza.push_back(make_pair(p,q)); } sort(seiza.begin(), seiza.end(), comp); for(int i = 1; i < seiza.size(); i++){ d.push_back(make_pair(seiza[i].first - seiza[0].first, seiza[i].second - seiza[0].second)); } scanf("%d", &n); for(int i = 0; i < n; i++){ int p, q; scanf("%d %d", &p, &q); cst.push_back(make_pair(p,q)); star[make_pair(p,q)]++; } for(int i = 0; i < n; i++){ tmp = 0; for(int j = 0; j < d.size(); j++){ if(!(cst[i].first >= -1 * (d[j].first) && cst[i].first <= 1000000 - d[j].first)) break; if(!(cst[i].second >= -1 * (d[j].second) && cst[i].second <= 1000000 - d[j].second)) break; if(star.find(make_pair(cst[i].first + d[j].first, cst[i].second + d[j].second)) == star.end()) break; tmp++; } if(tmp == m - 1){ ans.first = cst[i].first - seiza[0].first; ans.second = cst[i].second - seiza[0].second; break; } } printf("%d %d\n", ans.first, ans.second); } return 0; }