問題文
天海王国将试射轨道炮(ElectroMagnetic Launcher)作为武器开发的成果。在试射期间作为障碍物放置 N 我们将进行一个实验,将所有铁板打孔。
在设计阶段,轨道炮具有穿透任意数量障碍物的能力。
然而,使用轨道炮发射子弹需要巨大的能量。
Daiki 的任务是提前计算摧毁所有障碍物所需的最少射击次数。
还为轨道炮开发了一个特殊的炮塔,使其可以向任何方向射击。
为简单起见,障碍物是平面上的线段,轨道炮是原点。 表示为 (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 行包含四个整数 ( -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
入力例2
2 5 -10 5 0 10 0 10 10
出力例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