2005mdd

Problem D: Area Separation　区画を分割

(-100,-100)、(100,-100)、(100,100)、(-100,100) を頂点とする正方形領域が、与えられた n 本の直線によっていくつに分割されているかを調べる。

入力

• 1行目に直線の数。0で終了。
• 続けて直線上の2点の座標。

出力

分割される領域の数。

解答例

• 解いていないが、1つの直線だと領域は2個に分割される。次に直線を引いて、前の直線と交点があったら2つ領域が増え、交点が無かったら1つ領域が増える。
• 同様に考えていくと、(新たに直線を引いたときにできる交点の数+1)この領域が増えることになる。
• つまり交点の数を求めることができれば解けるはず。