POJ 2684 - Polygonal Line Search

http://poj.org/problem?id=2684

概要，制約

日本語の問題文を参照． Problem B: Polygonal Line Search

解法

0度，90度，180度，270度回転させたもののいずれかが，相対的に同じように線を引いていたら同じ形状．

回転に加えて，折れ線が逆方向になっていることもあるので，計16通り試す．

 1 #include <iostream>
 2 #include <vector>
 3 #include <complex>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef complex<int> P;
 7 
 8 namespace std {
 9   bool operator<(const P& p, const P& q)
10   {
11     if (p.real() == q.real()) {
12       return p.imag() < q.imag();
13     } else {
14       return p.real() < q.real();
15     }
16   }
17 };
18 
19 void rotate(vector<P>& v)
20 {
21   for (vector<P>::iterator it(v.begin()); it != v.end(); ++it) {
22     *it = P(0, 1) * *it;
23   }
24 }
25 
26 bool fit(const vector<P>& a, const vector<P>& b)
27 {
28   const int dx = a[0].real() - b[0].real();
29   const int dy = a[0].imag() - b[0].imag();
30   for (int j = 1; j < a.size(); j++) {
31     const int x = a[j].real() - b[j].real();
32     const int y = a[j].imag() - b[j].imag();
33     if (x != dx || y != dy) {
34       return false;
35     }
36   }
37   return true;
38 }
39 
40 bool is_same(vector<P> base, vector<P> p)
41 {
42   if (base.size() != p.size()) {
43     return false;
44   }
45   for (int i = 0; i < 4; i++) {
46     vector<P> v(p);
47     if (fit(base, v)) {
48       return true;
49     }
50     reverse(v.begin(), v.end());
51     if (fit(base, v)) {
52       return true;
53     }
54     reverse(base.begin(), base.end());
55     if (fit(base, v)) {
56       return true;
57     }
58     reverse(v.begin(), v.end());
59     if (fit(base, v)) {
60       return true;
61     }
62     reverse(base.begin(), base.end());
63     rotate(p);
64   }
65   return false;
66 }
67 
68 int main()
69 {
70   int N;
71   while (cin >> N && N != 0) {
72     int m;
73     cin >> m;
74     vector<P> base(m);
75     for (int i = 0; i < m; i++) {
76       cin >> base[i].real() >> base[i].imag();
77     }
78 
79     for (int i = 0; i < N; i++) {
80       cin >> m;
81       vector<P> v(m);
82       for (int j = 0; j < m; j++) {
83         cin >> v[j].real() >> v[j].imag();
84       }
85       if (is_same(base, v)) {
86         cout << i+1 << endl;
87       }
88     }
89     cout << "+++++" << endl;
90   }
91   return 0;
92 }