いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

AOJ 1136 Polygonal Line Search

ICPC2005年国内予選のB問題でもあります。
30分ほどで解けました。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1136

方針としては、最初にもらった折れ線に8通りの変形します。
スタートとゴールをひっくりかえすが2。
回転が0,90,180,270で4。
あわせて8つ。

その際に、スタートを(0,0)に移動させておきます。
その後、回転行列

cos(theta)  sin(theta)
-sin(theta) cos(theta)

にtheta = pi/2を代入し、(x,y) = (y,-x)を得ます。
これにより、回転をおこないます。

あとは、各折れ線にたいして、正規化を行い、上記の8つにあるかどうかをチェックすればOKです。

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <stack>
#include <utility>
#include <numeric>
#include <algorithm>
#include <functional>
#include <cctype>
#include <complex>
#include <string>
#include <sstream>

using namespace std;

#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()
#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(it,container) for(typeof(container.begin()) it = container.begin(); \
                             it != container.end(); ++it)
#define mp(a,b) make_pair((a),(b))

typedef long long ll;
typedef complex<double> point;

// up right down left
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};

const double EPS = 1e-9;
const int days[]     = {31,28,31,30,31,30,31,31,30,31,30,31};
const int daysleap[] = {31,29,31,30,31,30,31,31,30,31,30,31};

int main(){
    while(true){
        int n;
        cin >> n;
        if(n==0) break;
        // from start to goal.
        vector<pair<int,int> > poly1;
        // from goal to start.
        vector<pair<int,int> > poly2;
        {
            int m;
            cin >> m;
            int fx,fy;
            rep(i,m){
                int x,y;
                cin >> x >> y;
                if(i==0){
                    fx = x;fy = y;
                }
                poly1.push_back(mp(x,y));
                poly1[i].first -= fx;
                poly1[i].second -= fy;
            }
        }
        poly2 = poly1;
        reverse(all(poly2));
        {
            int frx,fry;
            rep(i,poly2.size()){
                if(i==0){
                    frx = poly2[i].first;fry = poly2[i].second;
                }
                poly2[i].first -= frx;
                poly2[i].second -= fry;
            }
        }

        vector<vector<pair<int,int> > > polys(8);
        polys[0] = poly1;
        polys[4] = poly2;

        for(int i=1;i<4;i++){
            for(int j=0;j<polys[0].size();j++){
                int x = polys[i-1][j].second;
                int y = -polys[i-1][j].first;
                polys[i].push_back(mp(x,y));
            }
        }
        for(int i=5;i<8;i++){
            for(int j=0;j<polys[0].size();j++){
                int x = polys[i-1][j].second;
                int y = -polys[i-1][j].first;
                polys[i].push_back(mp(x,y));
            }
        }

        rep(nnnn,n){
            vector<pair<int,int> > V;
            int m;
            cin >> m;
            int fx,fy;
            rep(i,m){
                int x,y;
                cin >> x >> y;
                if(i==0){
                    fx = x;fy = y;
                }
                V.push_back(mp(x,y));
                V[i].first -= fx;
                V[i].second -= fy;
            }
            bool ok = false;
            for(int i=0;i<8;i++){
                if(m != polys[i].size()) continue;
                bool eq = true;
                for(int j=0;j<m;j++){
                    eq &= (polys[i][j] == V[j]);
                }
                if(eq) ok = true;
            }
            if(ok) cout << (nnnn+1) << endl;

        }
        cout << "+++++" << endl;
    }
    return 0;
}