AOJ 1136 - Polygonal Line Search

問題概要

折れ線0,1,….,nのn+1個の折れ線が与えられる。各折れ線はm個の頂点で構成される。折れ線を構成する各線分はx軸またはy軸に平行であり、頂点では必ず90°回転する。xy平面で回転または平行移動をして折れ線0と一致する折れ線iを出力せよ。テストケースの間は"+++++"と出力する。

制約

• 1 ≤ n ≤ 50
• 3 ≤ m ≤ 10
• -10000 < x < 10000
• -10000 < y < 10000

解法

平行移動は考えずに線分の長さと次の頂点への方向を比較すると簡単に実装できる。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 51
 
struct Point{
  int x,y;
  double dist(const Point &p){
    return abs(x-p.x)+abs(y-p.y);
  }
};
 
int N,m[MAX];
vector<Point> lines[MAX];
 
int getDir(Point &p1,Point &p2){
  if(p1.x == p2.x){
    return (p1.y < p2.y ? 0 : 2);
  }
  return (p1.x < p2.x ? 3 : 1);
}
 
bool equals(vector<Point> &l1,vector<Point> &l2){
  int s1 = l1.size(), s2 = l2.size();
  if(s1 != s2) return false;
  bool flg = false;
  int d1,d2,diff;
  for(int i = 0 ; i < s1-1 ; i++){
    if(l1[i].dist(l1[i+1]) != l2[i].dist(l2[i+1])){
      flg = true; break;
    }
    d1 = getDir(l1[i],l1[i+1]);
    d2 = getDir(l2[i],l2[i+1]);
    if(i > 0){
      if(diff != (d1-d2+4)%4){
        flg = true; break;
      }
    }else{
      diff = (d1-d2+4)%4;
    }
  }
  if(!flg) return true;
  flg = false;
  for(int i = s1-1 ; i > 0 ; i--){
    if(l1[s1-i-1].dist(l1[s1-i]) != l2[i].dist(l2[i-1])){
      flg = true; break;
    }
    d1 = getDir(l1[s1-i-1],l1[s1-i]);
    d2 = getDir(l2[i],l2[i-1]);
    if(i != s1-1){
      if(diff != (d1-d2+4)%4){
        flg = true;
        break;
      }
    }else{
      diff = (d1-d2+4)%4;
    }
  }
  return !flg;
}
 
int main(){
  while(cin >> N,N){
    for(int i = 0 ; i <= N ; i++){
      cin >> m[i]; lines[i].clear();
      for(int j = 0 ; j < m[i] ; j++){
        int x,y;
        cin >> x >> y;
        lines[i].push_back((Point){x,y});
      }
    }
    for(int i = 1 ; i <= N ; i++){
      if(equals(lines[0],lines[i])){
        cout << i << endl;
      }
    }
    cout << "+++++" << endl;
  }
  return 0;
}