下の図1のような
長方形の組合せからなる図形の面積を求めるプログラムを作成してください.
入力は0番の頂点の座標 (0,0) から時計回りで整数座標を与えます.
図3のような単純多角形の面積を求めるプログラムを作成してください.
なお,
与えられた座標を入力順にたどった辺で囲まれる図形が
単純多角形になるかを判定した上で,
その面積を求めるプログラムを作成してください.
アルゴリズム等解説:チーム名-algorithm
詳細説明
1.問1についての詳細説明
入力として与えられる点を順に v_0, v_1, v_2, ..., v_n-1 とする.
-
最初の点 v_0 の座標は必ず (0,0) である(と仮定してよい).
-
最後の点 v_n-1 の座標は必ず (a,0) である.
ただし,a は 1 以上 20 以下の整数(以下,変数の範囲はすべて同様).
-
最初の点 v_0 と最後の点 v_n-1 以外の点の y 座標は 1 以上である.
-
(v_0,v_1), (v_1,v_2), ..., (v_n-2,v_n-1), (v_n-1,v_0) の各辺は,
x 軸に並行か,または y 軸に並行な線分である.
つまり,
v_i = (a,b) のとき,v_i+1 は (a,y) か (x,b) のどちらかである.
さらに v_i+1 = (x,b) の場合には,x > a である.
-
v_i が必ずしも長方形の角にならない場合もある.
たとえば,(3,4), (5,4), (7,4), (7,6), ... となるような場合もある.
2.問2についての詳細説明
入力として与えられる点を順に v_0, v_1, v_2, ..., v_n-1 とする.
また,隣同士の点を結んだ線分
(v_0,v_1), (v_1,v_2), ..., (v_n-2,v_n-1), (v_n-1,v_0) を,
境界辺あるいは辺と呼ぶことにする.
また,
上記の辺の順序を境界辺の入力順と呼ぶ.
-
最初の点 v_0 の座標は必ず (0,0) である(と仮定してよい).
また,他の点の x 座標,y 座標は 0 以上である.
したがって,
入力順に境界辺を進んだとき,
その進行方向の右側が境界辺で囲まれる図形の内部である.
-
入力順に境界辺をつないで囲んだ図形を作ったとき,
その隣り合う境界辺のなす内角が,
すべて 180 度以下になっている図形が凸多角形である.
なお,
境界辺のなす内角とは,
ここでは境界辺を入力順で進んだとき,進行方向に対して右側の角のことである.
-
境界辺 (v_i-1,v_i), (v_i,v_i+1) のなす内角が 180 度となる場合もある.
つまり,v_i が線分 v_i-1,v_i+1 上にあるような場合である.
3.問3についての詳細説明
入力として与えられる点を順に v_0, v_1, v_2, ..., v_n-1 とする.
また,隣同士の点を結んだ線分
(v_0,v_1), (v_1,v_2), ..., (v_n-2,v_n-1), (v_n-1,v_0) を,
境界辺あるいは辺と呼ぶことにする.
また,
上記の辺の順序を境界辺の入力順と呼ぶ.
-
出力は,単純多角形でない場合には -1 を,
単純多角形の場合には面積を出すようにすること.
-
最初の点 v_0 の座標は必ず (0,0) である(と仮定してよい).
また,他の点の x 座標,y 座標は 0 以上である.
したがって,
入力順に境界辺を進んだとき,
その進行方向の右側が境界辺で囲まれる図形の内部である.
-
入力として与えられる点で囲まれる図形が単純多角形になるか?の判定では,
(1) 同じ点が二度以上現れない,
(2) 境界辺同士が交差しない,
ことを調べればよい.
ただし,今回は (1) は仮定してよいので,
調べることは境界辺同士が交差しないことだけで十分である.
なお,厳密には,
境界辺同士が交差するとは,
その両端点以外で共通な点を持つことである.
つまり,
厳密には
下図4の (a), (b), (c) のようなパターンが起きるかを調べなければならないが,
この問では (a) のみを調べればよいことにする
((b) や (c) が生じるような入力データは審査には用いない).
-
二つの境界辺 (v_i-1,v_i), (v_i,v_i+1) が直線をなす場合もある.
つまり,v_i が線分 v_i-1,v_i+1 上にあるような場合である.
![figure3-pgon](cross.png)
図4 様々な交差の例
(a) 通常の交差:端点以外で共通な点を,ただ 1 つ持つ.
(b) 線分 1,2 と 3,4 が端点 3 で交わる.
(c) 線分 1,2 と 3,4 が重なる.