第7回日本情報オリンピック予選 問4

問題

• 第７回日本情報オリンピック予選 問4

std::vectorを利用して簡潔に．

簡潔に書けると気持ちが良いですね．

 #include <iostream>
 #include <algorithm>
 #include <vector>
 using namespace std;
 
 class pos {
 public:
      int x, y;
 
      pos()            { x = 0; y = 0; }
      pos(int a, int b){ x = a; y = b; }
 
      void put      (void)         { cout << x << " " << y << endl; }
      void operator=(const pos& p) { x = p.x; y = p.y; }
      int  operator==(const pos& p){ return (x == p.x && y == p.y); }
      int  operator!=(const pos& p){ return !(x == p.x && y == p.y); }
      pos  operator-(const pos& p) { return pos(x - p.x, y - p.y); }
      pos  operator+(const pos& p) { return pos(x + p.x, y + p.y); }
 };
 
 vector<pos> input(void){
      vector<pos> ret;
      int tmp, x, y;
      cin >> tmp;
      while(tmp--){
           cin >> x >> y;
           ret.push_back(pos(x,y));
      }
      return ret;
 }
 
 int main(void) {
      vector<pos> tar = input();
      vector<pos> src = input();
      pos diff;
 
      for(int sid = 0; sid < src.size(); sid++){
           for(int tid = 0; tid < tar.size(); tid++){
                if(tid == 0) diff = src[sid] - tar[tid];
                if(find(src.begin(), src.end(), tar[tid] + diff) == src.end()) break;
                if(tid == tar.size() - 1) diff.put();
           }
      }
 
      return 0;
 }

multimapを使って強引に．（最初に書いたやつ）

読みにくい．

 #include <iostream>
 #include <map>
 #include <algorithm>
 
 using namespace std;
 typedef multimap<int,int>::iterator mmapiter;
 
 multimap<int,int> tar,src;
 int tarx,tary,ansx,ansy;
 
 void input(void){
         int ntar,nsrc,x,y;
 
         cin >> ntar;
         for(int i=0;i<ntar;i++){
                 cin >> x >> y;
                 if(!i){
                         tarx = x;
                         tary = y;
                 }else{
                         tar.insert(pair<int,int>(x-tarx, y-tary));
                 }
         }
 
         cin >> nsrc;
         while(nsrc--){
                 cin >> x >> y;
                 src.insert(pair<int,int>(x, y));
         }
 }
 
 int is_exist(int x,int y){
         pair<mmapiter,mmapiter> p = src.equal_range(x);
 
         for(mmapiter i = p.first;i != p.second;i++){
                 if(i -> second == y){
                         return 1;
                 }
         }
         return 0;
 }
 
 void search(void){
         for(mmapiter psrc = src.begin(); psrc != src.end(); psrc++){
                 for(mmapiter ptar = tar.begin();is_exist(psrc -> first + ptar -> first , psrc -> second + ptar -> second);ptar++ ){
                         if(ptar == max_element(tar.begin(),tar.end())){
                                 ansx = psrc -> first;
                                 ansy = psrc -> second;
                                 return;
                         }
                 }
         }
 }
 
 int main(void){
         input();
         search();        
 
         cout << ansx - tarx  << " " << ansy - tary << endl;
 
         return 0;
 }