Problem 1136 : Polygonal Line Search

keyword

幾何　C++

概要

直線から構成された図形が与えられる。合同な図形を判定する問題。直線はすべてX or Y軸に平行。
端点を原点に平行移動して回転させてやればよい。

vector<pair<int,int> > rot(vector<pair<int,int> > ps){
    int i, s=SZ(ps);
    REP(i,s){
        swap(ps[i].first, ps[i].second);
        ps[i].first *= -1;
    }
    REP(i,s){
        ps[s-1-i].first  -= ps[0].first;
        ps[s-1-i].second -= ps[0].second;
    }
    return ps;
}

int main(){
    int n, m, i, j, k, x, y;

    while(scanf("%d",&n)){
        if(!n) break;
        scanf("%d",&m);
        vector< pair<int,int> > origin;
        vector<int> ans;
        vector< vector< vector<pair<int, int> > > > polys(n);
        REP(i,m){
            scanf("%d%d",&x,&y);
            origin.PB(MP(x,y));
        }
        REP(i,m){
            origin[m-1-i].first  -= origin[0].first;
            origin[m-1-i].second -= origin[0].second;
        }

        REP(i,n){
            scanf("%d",&m);
            polys[i].PB(vector< pair<int, int> >());
            REP(j,m){
                scanf("%d%d",&x,&y);
                polys[i][0].PB(MP(x,y));
            }
            REP(j,3) polys[i].PB(rot(polys[i].back()));
            polys[i].PB(polys[i][0]);
            reverse(polys[i].back().begin(), polys[i].back().end());
            REP(j,m){
                polys[i].back()[m-1-j].first -= polys[i].back()[0].first;
                polys[i].back()[m-1-j].second-= polys[i].back()[0].second;
            }
            REP(j,3) polys[i].PB(rot(polys[i].back()));
        }

        REP(i,n){
            REP(k,4){
                origin = rot(origin);
                REP(j,8)if(polys[i][j] == origin) goto end;
            }
end:;
            if(j<8) ans.PB(i);
        }
        REP(i,SZ(ans)){
            printf("%d\n",ans[i]+1);
        }
        printf("+++++\n");
    }

    return 0;
}