以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Lines: 直線
input ファイル“lines.in”
output 標準出力
ソースファイルlines.c/lines.cpp/Lines.java
時間制限1 秒/ データ
平面上のN 本の直線ℓ1, ℓ2, . . . , ℓN が入力として与えられる.これらの直線によって平面を分
割したときの領域の個数を求めるプログラムを作成せよ.ただし,これらの直線には重複があ
るかもしれない.
下図では14 個の領域に分割されている.
ℓ1
ℓ2
ℓ3
ℓ4 ℓ5
Input.入力はファイルは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)) が空白を区切りとして書かれている.これは,直線ℓi が,
点Pi(ai, bi) と点Qi(ci, di) を結ぶ直線であることを意味している.
Output.標準出力に1 行で領域の個数を出力せよ.
直線–1/2
例
lines.in 標準出力
4 11
0 4 6 4
0 0 6 6
1 0 1 6
0 6 6 0
Q3 Q2
P4
P1 Q1
ℓ1
P2 P3
Q4
ℓ2 ℓ3 ℓ4
直線–2/2