2003/Contest/会津大会

Problem C : Area of Polygons †

問題概要 †

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

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

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

解法 †

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

その直後に、

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

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

議論・その他 †

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

---

ファイルを添付する †

terashima_area.cpp 1127件 [詳細] noda_area.cpp 1665件 [詳細] mikurube_Error_C.cpp 1702件 [詳細] area.sample.out.txt 934件 [詳細] area.sample.txt 863件 [詳細] area.txt 881件 [詳細] area.out.txt 1024件 [詳細] deadbeef_TLE_C.java 1079件 [詳細] vertices_TLE_C.c 912件 [詳細] izumi_C.cpp 1277件 [詳細]

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。
添付ファイル:
管理者パスワード: Rename the filename to: