Problem C : Area of Polygons †問題概要 †頂点の座標が整数の (凸とは限らない) 多角形が与えられ、その面積の概数を求める。 正確には、与えられた多角形のわずか一部でも含んでいる整数格子上の単位正方形、の個数を求める。 本番では 3 チームが正解。 解法 †本番では、思わず多角形の Bounding Box 中の全セルに対して含まれる・含まれないを判定するプログラムを書いてしまったのだが、 (-2000, -2000) 〜 (2000, 2000) という広大な領域を対象としては Time-Limit Exceeded となってしまった。計算量のことをもう少し意識しましょう。 > 自分 その直後に、 整数格子の単位正方形、ある横一列について、ある多角形の辺が横切っているマス群の範囲をリストにして保存。 そのリストをソートし、奇数番目の左端から偶数番目の右端までは多角形に含まれている、と考える。 という基本方針を考えついたものの残り三十分未満。慌ててしまったことも手伝って、実装する時間が足りず終了。 (三廻部) 議論・その他 †
ファイルを添付する †terashima_area.cpp 1194件 [詳細] noda_area.cpp 1805件 [詳細] mikurube_Error_C.cpp 1824件 [詳細] area.sample.out.txt 974件 [詳細] area.sample.txt 913件 [詳細] area.txt 929件 [詳細] area.out.txt 1078件 [詳細] deadbeef_TLE_C.java 1128件 [詳細] vertices_TLE_C.c 956件 [詳細] izumi_C.cpp 1349件 [詳細] |