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)

ファイルを添付する †

B1.out

B2.out

hirano_B.cpp

mikurube_b.c

usaP_B.cpp

doorgod_B.cpp