Railroad Conflict 解説
- 問題名:Railroad Conflict
- 出典:Problem D, ACM/ICPC Practice Contest for Japan Domestic, 2006-06-18
- 難易度:☆☆☆
- 問題の種類:幾何
- 解法:線分の交点順にソート
- 解答ソースコード:
- OB/OGの会の解説:p0103-obog.pdf
アルゴリズムの概略
与えられた問題そのままを実装すればOKです。 つまり,各線分との交差判定+交点計算を行い, それらの交点を新線の開始点からの距離でソートしておいて, 新線の開始点から近い順に(遠い順からでもOK)交点を見ていって地上と地下を反転する回数を数え上げます。
アルゴリズムの計算量
線分の交差判定は新線に対して旧線をそれぞれ一回ずつ判定すればいいので O(n) です(交差判定と交点計算は O(1) なので)。 出てくる交点の数は最大 n です。 交点のソートは組み込みのクイックソートを使って O(n log2 2) としましょう。 最後に交点を全て順に見ていくだけなので O(n) です。 結局,ほとんどが O(n) で済みます。 n = 100 なので計算量は問題となりません。
アルゴリズムの実装
二つの線分が平行で重なっているときに注意してください。 幾何問題では例外を見落としやすいのでよく確認する必要があります。
$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $