2002/Contest/世界大会

Problem E : Covering Whole Holes

問題概要

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

解法

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

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

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

議論

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

ファイルを添付する

filemikurube_e.c 692件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filemikurube_e.c 692件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:50 (3243d)