2003/Contest/会津大会

Problem C : Area of Polygons

問題概要

頂点の座標が整数の (凸とは限らない) 多角形が与えられ、その面積の概数を求める。

正確には、与えられた多角形のわずか一部でも含んでいる整数格子上の単位正方形、の個数を求める。

本番では 3 チームが正解。

解法

本番では、思わず多角形の Bounding Box 中の全セルに対して含まれる・含まれないを判定するプログラムを書いてしまったのだが、 (-2000, -2000) 〜 (2000, 2000) という広大な領域を対象としては Time-Limit Exceeded となってしまった。計算量のことをもう少し意識しましょう。 > 自分

その直後に、

整数格子の単位正方形、ある横一列について、ある多角形の辺が横切っているマス群の範囲をリストにして保存。
そのリストをソートし、奇数番目の左端から偶数番目の右端までは多角形に含まれている、と考える。

という基本方針を考えついたものの残り三十分未満。慌ててしまったことも手伝って、実装する時間が足りず終了。 (三廻部)

議論・その他

  • 上の記述で三廻部が述べている方針は一見すると大がかりな実装が必要なようにも見えるが、うまく書けば 60 行ちょっとのコードで実装可能。izumi_C.cpp を参照。(泉)
  • 三廻部のプログラムは誤差関係でどこかミスってるらしく、環境によって結果がずれたりする。 (三廻部; Dec 15, 2005)

ファイルを添付する

fileterashima_area.cpp 1194件 [詳細] filenoda_area.cpp 1805件 [詳細] filemikurube_Error_C.cpp 1824件 [詳細] filearea.sample.out.txt 974件 [詳細] filearea.sample.txt 913件 [詳細] filearea.txt 929件 [詳細] filearea.out.txt 1078件 [詳細] filedeadbeef_TLE_C.java 1128件 [詳細] filevertices_TLE_C.c 956件 [詳細] fileizumi_C.cpp 1349件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileterashima_area.cpp 1194件 [詳細] filenoda_area.cpp 1805件 [詳細] filemikurube_Error_C.cpp 1824件 [詳細] filearea.sample.out.txt 974件 [詳細] filearea.sample.txt 913件 [詳細] filearea.txt 929件 [詳細] filearea.out.txt 1078件 [詳細] filedeadbeef_TLE_C.java 1128件 [詳細] filevertices_TLE_C.c 956件 [詳細] fileizumi_C.cpp 1349件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:46 (5477d)