2005/Contest/国内予選

Problem B : Polygonal Line Search

問題概要

解法

比較する折れ線の片方を、

  • 90 度回転 (4 パターン)
  • 点の並びの向きを逆にする (2 パターン)

の両方、計 8 パターンに変形し、比較を行う。後者くらいなら、比較時に変数回す向きを変える、とかでも十分。

この時、座標を適当に正規化するのも忘れずに。(折れ線の左上を (0,0) に合わせるとか、座標の相対位置だけ保存するようにするとか、いくつか方法がある)

目標は 20 分。 (三廻部; Jul 2, 2005)

議論・その他

  • 30 分。がーん。 17 〜 18 分であらかた書けてたんだけど、一箇所ミスを。 (関数 reverse() 中で y 座標の方を操作するのを忘れてた。間抜け...) (三廻部; Jul 2, 2005)

ファイルを添付する

fileB1.out 836件 [詳細] fileB2.out 832件 [詳細] filehirano_B.cpp 959件 [詳細] filemikurube_b.c 1055件 [詳細] fileusaP_B.cpp 732件 [詳細] filedoorgod_B.cpp 789件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileB1.out 836件 [詳細] fileB2.out 832件 [詳細] filehirano_B.cpp 959件 [詳細] filemikurube_b.c 1055件 [詳細] fileusaP_B.cpp 732件 [詳細] filedoorgod_B.cpp 789件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:36 (4343d)