AOJ 1136: Polygonal Line Search

問題

Polygonal Line Search | Aizu Online Judge

与えられた折れ線と同じ形状の折れ線の番号をすべて答えよ

方針

• 折れ線を(次に曲がる向き, 線分の長さ）のvectorとして保持し、テンプレートと比較する
• 向きは1: 右折、-1: 左折、0: 終わりとした
• 後ろから逆向きに比較しないと一致が判定できない場合もあるので、後ろ向きの比較も行う

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

class P{
public:
    int x, y;
    P(int x, int y): x(x), y(y){};
};
int main(void){
    int n;
    while(cin >> n && n) {
        vector<vector<P> > line;
        rep(l, n+1) {
            int m, x, y;
            cin >> m;
            vector<P> tmp;
            rep(i, m) {
                cin >> x >> y;
                tmp.push_back(P(x, y));
            }
            vector<P> tmp2;
            rep(i, m-1) {
                int d;
                if(i==m-2) {
                    d = 0;
                } else if((tmp[i+1].x==tmp[i].x && tmp[i+1].y>tmp[i].y &&
                        tmp[i+2].x>tmp[i+1].x && tmp[i+2].y==tmp[i+1].y) ||
                       (tmp[i+1].y==tmp[i].y && tmp[i+1].x>tmp[i].x &&
                        tmp[i+2].x==tmp[i+1].x && tmp[i+2].y<tmp[i+1].y) ||
                       (tmp[i+1].x==tmp[i].x && tmp[i+1].y<tmp[i].y &&
                        tmp[i+2].y==tmp[i+1].y && tmp[i+2].x<tmp[i+1].x) ||
                       (tmp[i+1].y==tmp[i].y && tmp[i+1].x<tmp[i].x &&
                        tmp[i+2].x==tmp[i+1].x && tmp[i+2].y>tmp[i+1].y)) {
                    d = 1;
                } else {
                    d = -1;
                }
                tmp2.push_back(P(d, abs(tmp[i+1].x-tmp[i].x)
                                    +abs(tmp[i+1].y-tmp[i].y)));
            }
            line.push_back(tmp2);
        }
        for(int i=1; i<line.size(); ++i) {
            bool same, same1, same2;
            same = same1 = same2 = true;
            int len;
            if(line[i].size() != line[0].size()) same = false;
            else {
                len = line[0].size();
            }
            rep(j, len) {
                if(line[i][j].x!=line[0][j].x || line[i][j].y!=line[0][j].y) {
                    same1 = false; break;
                }
            }
            rep(j, len) {
                if(line[i][len-j-1].y!=line[0][j].y) {
                    same2 = false; break;
                }
                if(j<len-1) {
                    if(line[i][len-j-2].x==line[0][j].x) {
                        same2 = false; break;
                    }
                }
            }
            if(same && (same1 || same2)) cout << i << endl;
        }
        cout << "+++++" << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1898522

反省

• 向きの判定は

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);
}

（ttp://arrows1011.hatenablog.com/entry/2014/12/07/042628 より） とかの短い書き方があった（賢いなぁ）