直線 (Lines)
時間制限 : 1sec / スタック制限 : 64MB / メモリ制限 : 64MB
平面上のN 本の直線l1, l2, … , lN が入力として与えられる．これらの直線によって平面を分割したときの領域の個数を求めるプログラムを作成せよ．ただし， これらの直線には重複があるかもしれない．
下図では14 個の領域に分割されている．
入力
入力はファイルはlines.in である．入力はN + 1 行からなる．最初の行にN (1 ≦ N ≦ 1000) の値が書かれている．i + 1 行目(1 ≦ i ≦ N) には，4 つの整数ai, bi, ci, di (0 ≦ ai, bi, ci, di ≦ 1000, (ai, bi) ≠ (ci, di)) が空白を区切りとして書かれている．これは，直線li が，点Pi(ai, bi) と点Qi(ci, di) を結ぶ直線であることを意味している.
出力
標準出力に1 行で領域の個数を出力せよ．
入出力例
| 入力例1 |
出力例1 |
4
0 4 6 4
0 0 6 6
1 0 1 6
0 6 6 0 |
11 |
コメント
最終更新：2013年02月23日 23:37
