AOJ1136 Polygonal Line Search ~ 座標を90度回転させたくなったので ~

問題

Polygonal Line Search

方針

・比較対象を90度ずつ回転させて始点を元の図に合わせてひたすら判定を繰り返す.
・後ろから比較しないと一致しない場合があるのでそれを考慮する.
計算量的に泥臭く書いてもTLEしないと思うので実装を頑張る.

座標の90度回転

自分はcmathのsinとかcon関数を使ってよしなにする方法を真っ先に思いついたけど,よくよく考えてみると90度時計回りの回転なので

x = y
y = -x

で実現できる.証明とかはググれば出てくると思う.

回答コード

bool check(vector<pi> comp, vector<pi> target){
    if(comp.size()!=target.size())return false;
    for(int z=0;z<2;z++){
        for(int i=0;i<4;i++){
            bool ok=true;
            int x=target[0].first-comp[0].first;
            int y=target[0].second-comp[0].second;
            for(int j=0;j<(int)comp.size();j++){
                if(comp[j].first+x!=target[j].first||comp[j].second+y!=target[j].second){
                    ok=false;
                }
                int tmp=-target[j].first;
                target[j].first=target[j].second;
                target[j].second=tmp;
            }
            if(ok)return true;
        }
        reverse(all(target));
    }
    return false;
}

void solve(int n){
    int m;
    cin>>m;

    vector<pi> comp(m);
    for(int i=0;i<m;i++){
        cin>>comp[i].first>>comp[i].second;
    }

    for(int i=0;i<n;i++){
        cin>>m;
        vector<pi> diff(m);
        for(int j=0;j<m;j++){
            cin>>diff[j].first>>diff[j].second;
        }
        if(check(comp,diff))cout<<i+1<<endl;
    }
}

int main(){
    int n;
    while(cin>>n){
        if(n==0)break;
        solve(n);
        cout<<"+++++"<<endl;
    }
    return 0;
}

終わりに

色々解説見たけど,この解法が一番シンプルでバグを埋め込みにくい気がする.
それから,実はこの問題は半年前に挑戦してWA出しまくって解けなかった問題だったりする.
以前は90度回転解法ではなくて,「どの向きにどれだけ移動しているか」みたいな方針で解いていたので,割と複雑なコードになってバグを埋め込みまくった挙句リタイアしていたなぁ...