← 返回题目列表

AtCoder · joisc2007_lines

lines. 线

中文机器翻译题面 查看原题

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

直線 (Lines) - 原题 PDF 第 1 页
原题PDF第3页
直線 (Lines) - 原题 PDF 第 2 页
原始 PDF 第 4 部分
可复制的 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