D - EMLauncher Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

天下一王国では兵器開発の成果としてレールガン (ElectroMagneticLauncher) の試射が行われます。
試射では障害物として配置された N 枚の鉄板を全て打ち抜く実験を行います。
設計段階ではいくらでも障害物を貫通させるだけの威力を、レールガンは備えています。
しかし、レールガンを用いて弾体を射出するには膨大な電力が必要りなります。
ダイキ君は前もって全ての障害物を破壊するために必要な最小の発射回数を計算する仕事を任されました。
また、レールガンは専用の砲座も開発されており、任意の方角へ向けての射出が可能です。

簡単のために、障害物は平面上の線分、レールガンは原点 (0, 0) として表現されます。
発射された弾体の軌道は原点から延びる半直線として表され、交差または接した障害物を全て破壊します。

入力

入力は以下の形式で標準入力から与えられる。
N
X_{1,1} Y_{1,1} X_{1,2} Y_{1,2}
X_{2,1} Y_{2,1} X_{2,2} Y_{2,2}
:
X_{N,1} Y_{N,1} X_{N,2} Y_{N,2}
  • 1 行目には配置される障害物の数 N ( 1 ≦ N ≦ 2000 ) が与えられる
  • 2 行目から N 行目には4つの整数 ( -1000 ≦ X_{i,1}, Y_{i,1}, X_{i,2}, Y_{i,2} ≦ 1000 ) が与えられ、 i 行目は i 番目の障害物の端点が (X_{i,1}, Y_{i,1}) と (X_{i,2}, Y_{i,2}) であることを表しています
  • 障害物（端点を含む）が原点に接することはない
  • 障害物（端点を含む）が互いに交差したり接したりすることはない

部分点

  • N ≦ 20 の全てのテストケースに正解した場合、部分点として 45 点があたえられる
  • N ≦ 200 の全てのテストケースに正解した場合、部分点として さらに 40 点があたえられる

出力

全ての障害物を破壊するために必要な試射の回数を 1 行に出力せよ。出力の末尾には改行を入れること。

入力例1

2
10 10 10 -10
-10 10 -10 -10

出力例1

2
図1
赤線の方向に試射することで、2回で破壊することができます。

入力例2

2
5 -10 5 0
10 0 10 10

出力例2

1
図2
赤線に対して2つの障害物が触れているので、1回で破壊することができます。

入力例3

8
1 5 6 1
6 -1 1 -6
-1 -6 -5 -1
-5 1 -1 5
7 5 7 -6
-5 -7 6 -7
-6 -6 -6 5
-5 6 6 6

出力例3

4
図3
赤線の方向に試射することで、4回で破壊することができます。

Source Name

天下一プログラマーコンテスト2014 予選A