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 より) とかの短い書き方があった(賢いなぁ)