10万本の棒の交差判定

ICPC勉強会、4月の模擬戦でした。
レベルが均等になるようにと組まれたペアですが、私のお相方は一つ上の主席の先輩…恐れ多い。
今回は全文英語のまま。ただし辞書の使用可、Javadocの参照可。でももちろんパソコンは一台です。
問題のレベルが高かったような気がする。A問題は単純な計算ですぐ解けて、B問題は文字列生成で再帰。
後者のコーディングは先輩に任せていたんだけれど、途中でバックトラックについて聞かれてオドオドしながらメソッドを書くことに。
バックトラックって、コードで見るとわかりにくい気がする。同じ再帰でも、DFSはわりとわかりやすい。
C問題は直線の交差判定だったのですが、なんか少年が部屋で床に棒を投げる話。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2653
で、この棒の本数が最大で10万本。ありえない。1秒に1回投げても10日じゃ終わらない。この少年確実に狂ってる。
まぁ要はその10万という数がポイントでして、普通のごり押しだと時間超過かメモリオーバーを起こします。
交差判定を後ろから進めていくとか、同じ大きさのboolean配列を使うとか、そんな工夫が必要。
D、E、Fは宿題になりました。二分法とかDPとかです。未だにDPを1から書けてない…

今回は他研の先輩が参加していて楽しかったです。