【AOJ 1136】Polygonal Line Search

問題

Polygonal Line Search | Aizu Online Judge

方針

• 0番目の入力セットと1〜n番目までのセットを比較して同じ形の折れ線であるか判定する.
• 同じ折れ線であるかの判定は, 以下のいずれかを満たす.
  1. xy平面内で回転および平行移動によって(拡大縮小や裏返しをせずに)重なり合う
  2. 始点から終点まで の頂点が逆順に指定されている
• 90度ごとにしか回転しない（1セットについて高々4パターン）ので, 4回転全部試してみる.
• 比較する際に始点を合わせる（これ合わせなくても行けそうだなと思ったけど頭がなかった）
• 入力形式ちゃんと読んでなくてバグらせて辛かった(n+1セット分入力があるのをすっかり見落としていた）

コード

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<memory>
#include<functional>

#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef pair<int, int> pii;

vector<pii> in[50];
int m[50];

bool equal(vector<pii> v1, vector<pii> v2){
  int dx = (v1[0].first - v2[0].first);
  int dy = (v1[0].second - v2[0].second);
  rep(i, v1.size()){
    if(v1[i].first != v2[i].first+dx || v1[i].second != v2[i].second+dy) return false;
  }
  return true;
}

bool solve(int n){
  // 線分の数が異なる時は一致しない
  if(in[0].size() != in[n].size()) return false;  
  rep(i, 2){    // 順方向, 逆方向
    rep(j, 4){ // 4回転
      if(equal(in[0], in[n])) return true;         
      rep(k, m[n]){
        swap(in[n][k].first, in[n][k].second);
        in[n][k].first *= -1;
      }
    }
    reverse(ALL(in[n]));
  }
  return false;
}

signed main(){
  int n;

  int x, y;

  
  while(cin >> n, n){
    
    // 入力
    rep(i, n+1){
      cin >> m[i];
      in[i].clear();
      rep(j, m[i]){
        cin >> x >> y;
        in[i].pb(mp(x, y)); 
      }
    }

    REP(i, 1, n+1){
      if(solve(i)) cout << i << endl;
    }
    cout << "+++++" << endl;
  }
  
}