2005db

Problem B: Polygonal Line Search 折れ線の探索

ある折れ線が与えられて、それと同じ折れ線を見つける問題。折れ線は90度で曲がる。拡大縮小、裏返しは無し。回転は90度単位。

入力

• まず探索する折れ線の数。
  • お手本の折れ線データ
    • 最初に座標の数m、続いてx,y座標
  • 探索する折れ線データ(n個)
    • 最初に座標の数m、続いてx,y座標

解答例

• 裏返しが無いのだから、座標を上手く統一させて（正規化 by コンピュータビジョンの授業）90度回転を4回やって重なるかどうかで判定できるかな？
  • 見本の最初の点を原点にして、その他の折れ線も最初の点と最後の点を原点にして同じかどうか確認する。
  • 順番が逆になる場合もあるので考慮する。(0,0)-(2,0)-(2,2) と (2,2)-(2,0)-(0,0) は同じ。
  • 90度回転は次の式で（by コンピュータビジョンの授業）

          x' = cos90*x - sin90*y = -y
          y' = sin90*x + cos90*y = x

• 05db2.c 無駄が多いけど、できてるようだ。