- 2005-06-05 (Sun) 12:50
- アカデミック？
格子点上に頂点を持つ多角形の面積と内部の格子点数と辺の上に載っている格子点数の間には関係式がある．
「Ｐｉｃｋの定理」 平面上の格子多角形 P に対して，辺上にある格子点の個数を b, P の内部格子点数を c とすると, その面積 S(P) は次式となる: S(M) = (c-1) + b/2 .
基本的なアイデアは多角形を面積が 1/2 の三角形に分解していくイメージのはず．とりあえず，この定理を知っていると格子点上の図形問題が格段に簡単に解けるに違いない．
- Newer: PPoPP は Practice を結構重んじる