← 返回题目列表

AtCoder · tenka1_2014_qualA_d

D. EM 启动器

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

問題文

天海王国将试射轨道炮(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
図1
朝红线方向射击,可以用两次射击将其摧毁。

入力例2

2
5 -10 5 0
10 0 10 10

出力例2

1
図2
有两个障碍物触及红线,所以你可以一口气摧毁它们。

入力例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次即可将其摧毁。