2002/Contest/世界大会

Problem E : Covering Whole Holes †

問題概要 †

水平線と垂直線からなる二つの多角形があり、一方がもう一方を内包できるかどうか調べる。

解法 †

座標に制限が無いため、 1 ずつずらして探したりするとはまるのは確実。

内包できる場合、水平線と垂直線それぞれがどこか一箇所で重なった状態で内包することができるはず、という (おそらく) 事実に基づいて探索を行った。

計算量 : O( (辺の数)^5 ) かな。オーダーでなければ (カバーの辺の数/2)^2 * (穴の辺の数/2)^2 * (穴の点の数) だけど。 (三廻部; Mar 19, 2004)

議論 †

• 結構簡単だった気が。問題読み〜思考に二十分、コーディングに三十分。まあ、合っているかどうかはわからないわけだけど。
  去年、本番でこれ解いたっけ...? (三廻部; Mar 19, 2004)

ファイルを添付する †

mikurube_e.c