- 追加された行はこのように表示されます。
- 削除された行は
このように表示されます。
!!Problem B: Polygonal Line Search 折れ線の探索
ある折れ線が与えられて、それと同じ折れ線を見つける問題。折れ線は90度で曲がる。
拡大縮小、裏返しは無し。回転は90度単位。
!入力
*まず探索する折れ線の数。
**お手本の折れ線データ
***最初に座標の数m、続いてx,y座標
**探索する折れ線データ(n個)
***最初に座標の数m、続いてx,y座標
!解答例
*裏返しが無いのだから、座標を上手く統一させて90度回転を4回やって重なるかどうかで判定できるかな？
*裏返しが無いのだから、座標を上手く統一させて（正規化 by コンピュータビジョンの授業）90度回転を4回やって重なるかどうかで判定できるかな？
**見本の最初の点を原点にして、その他の折れ線も最初の点と最後の点を原点にして同じかどうか確認する。
**順番が逆になる場合もあるので考慮する。(0,0)-(2,0)-(2,2) と (2,2)-(2,0)-(0,0) は同じ。
**90度回転は次の式で
**90度回転は次の式で（by コンピュータビジョンの授業）
x' = cos90*x - sin90*y = -y
y' = sin90*x + cos90*y = x
*[[05db2.c]] 無駄が多いけど、できてるようだ。