スーパーコン０８予選問題ならびにスーパーコン認定問題

問１（スーパーコン３級認定問題 2008 年度版）

下の図１のような 長方形の組合せからなる図形の面積を求めるプログラムを作成してください． 入力は0番の頂点の座標 (0,0) から時計回りで整数座標を与えます．

図１　棒グラフのような長方形の集まり．

詳細説明：

• すべての問いに共通な詳細説明
• 問１についての詳細説明

問２（スーパーコン２級認定問題 2008 年度版）

下の図２のような 凸多角形の面積を求めるプログラムを作成してください． 入力は0番の頂点の座標から時計回りで整数座標を与えます．

図２　凸多角形

詳細説明：

• すべての問いに共通な詳細説明
• 問２についての詳細説明

問３（スーパーコン１級認定問題 2008 年度版＆スーパーコン０８予選問題）

図３のような単純多角形の面積を求めるプログラムを作成してください． なお， 与えられた座標を入力順にたどった辺で囲まれる図形が 単純多角形になるかを判定した上で， その面積を求めるプログラムを作成してください．

図３　単純多角形

詳細説明：

• すべての問いに共通な詳細説明
• 問３についての詳細説明

1. 作成するプログラム

1. プログラムは入出力の部分を規定した 雛形プログラムをもとに， その一部を修正する形で作ること． 作成の際には， 「変更・削除しないこと」とコメントされている行は変更・削除しないこと．したがって，ここで指定された入力，出力以外のものを期待したプログラムは審査対象から除外されます． その他は適宜変更や追加して構わない． また，関数等を宣言して使用しても構わない．
2. プログラムはヘッダーファイル等は使わずに１つのファイルとして まとめたものを提出すること （詳しくは，最下段，４．提出物の項目を参考のこと）
3. プログラムは，ANSI C に準拠するＣ言語で記述すること．
   • integer 32bit，long 64bitを仮定．
   • gcc ver 3.3.3を使用してコンパイルする．
   • Endianの違いによるトラブルに対しては対処しない．

2. 入力データの形

1. 点は二次元平面上の x 座標，y 座標で与える． 座標はすべて 0 以上 R 以下の整数とする （問１では R = 20，問２，問３では R = 500 とする）．
2. 以下の説明では， 点を入力の順に v_0, v_1, v_2, ..., v_n-1 と呼ぶ． n は入力される点の個数である （問１では n は 50 以下，問２，問３では n は 20,000 以下とする）．
3. v_0, v_1, v_2, ..., v_n-1 中に同じ座標の点はない（と仮定してよい）．
4. 求める面積は， v_0, v_1, v_2, ..., v_n-1, v_0 で辺を描いたときに， その辺で囲まれる図形の面積である．
5. 入力（そして出力）は次の例のような形式で標準入力から与える． 詳細は雛形プログラムを参照．

   0 0
   0 3
   2 3
   2 5
   11 5
   11 0
   -1 -1　　　←データ終了の印

3. 審査方法

1. スーパーコン認定では， 応募プログラムをコンパイルし，複数のテストデータで実行し， そのテストデータで正確な答えを出している場合に合格とする． なお，誤差は認めない． （ヒント：問１の場合には，答えは整数になるはず． 問２，問３でも，答えはすべて 0.5 の倍数になるはずである．）
2. 各データに対し， 実行時間（壁時間）が１分を越えた場合には失格とする．
3. スーパーコン０８予選応募者に対しては， 複数個の審査用データに対して実行し， すべてで正確な答えを出したプログラムの中から， 実測した合計計算時間の順で， 東西の各々で上位１０チームを本選出場候補チームとして選ぶ． 本選出場候補チームには，同時に，スーパーコン１級も与える．

4.提出物

応募用紙(申込用紙に必要事項を記載し，テキストとしてファイルに落としたもの）： チーム名-oubo

解答プログラム： チーム名.c

プログラム実行環境（実行結果，時間，使用コンパイラ等)：チーム名-env

アルゴリズム等解説：チーム名-algorithm

詳細説明

１．問１についての詳細説明

入力として与えられる点を順に v_0, v_1, v_2, ..., v_n-1 とする．

1. 最初の点 v_0 の座標は必ず (0,0) である（と仮定してよい）．
2. 最後の点 v_n-1 の座標は必ず (a,0) である． ただし，a は 1 以上 20 以下の整数（以下，変数の範囲はすべて同様）．
3. 最初の点 v_0 と最後の点 v_n-1 以外の点の y 座標は 1 以上である．
4. (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 である．
5. v_i が必ずしも長方形の角にならない場合もある． たとえば，(3,4), (5,4), (7,4), (7,6), ... となるような場合もある．

２．問２についての詳細説明

入力として与えられる点を順に 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 以上である． したがって， 入力順に境界辺を進んだとき， その進行方向の右側が境界辺で囲まれる図形の内部である．
2. 入力順に境界辺をつないで囲んだ図形を作ったとき， その隣り合う境界辺のなす内角が， すべて 180 度以下になっている図形が凸多角形である． なお， 境界辺のなす内角とは， ここでは境界辺を入力順で進んだとき，進行方向に対して右側の角のことである．
3. 境界辺 (v_i-1,v_i), (v_i,v_i+1) のなす内角が 180 度となる場合もある． つまり，v_i が線分 v_i-1,v_i+1 上にあるような場合である．

３．問３についての詳細説明

入力として与えられる点を順に 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. 出力は，単純多角形でない場合には -1 を， 単純多角形の場合には面積を出すようにすること．
2. 最初の点 v_0 の座標は必ず (0,0) である（と仮定してよい）． また，他の点の x 座標，y 座標は 0 以上である． したがって， 入力順に境界辺を進んだとき， その進行方向の右側が境界辺で囲まれる図形の内部である．
3. 入力として与えられる点で囲まれる図形が単純多角形になるか？の判定では， (1) 同じ点が二度以上現れない， (2) 境界辺同士が交差しない， ことを調べればよい． ただし，今回は (1) は仮定してよいので， 調べることは境界辺同士が交差しないことだけで十分である． なお，厳密には， 境界辺同士が交差するとは， その両端点以外で共通な点を持つことである． つまり， 厳密には 下図４の (a), (b), (c) のようなパターンが起きるかを調べなければならないが， この問では (a) のみを調べればよいことにする （(b) や (c) が生じるような入力データは審査には用いない）．
4. 二つの境界辺 (v_i-1,v_i), (v_i,v_i+1) が直線をなす場合もある． つまり，v_i が線分 v_i-1,v_i+1 上にあるような場合である．

図４　様々な交差の例

(a) 通常の交差：端点以外で共通な点を，ただ 1 つ持つ．
(b) 線分 1,2 と 3,4 が端点 3 で交わる．
(c) 線分 1,2 と 3,4 が重なる．