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