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 1224件
[詳細]
B2.out 1223件
[詳細]
hirano_B.cpp 1357件
[詳細]
mikurube_b.c 1747件
[詳細]
usaP_B.cpp 950件
[詳細]
doorgod_B.cpp 1041件
[詳細]