两个朋友正在气泡星系中旅行。他们说“你好!”如果它们的距离小于或等于 $$$d_1$$$,则通过信号相互发送并且
- 这是他们第一次互相交谈或
- 在他们最后一次谈话后的某个时间点,他们的距离大于 $$$d_2$$$。
我们需要计算朋友说“你好!”的次数彼此。对于 $$$N$$$ 时刻,您将为每个朋友提供一个代表他们当时位置的积分数组。一个人可以在两个时刻之间保持在相同的位置,但是如果一个人做出了移动,我们假设该移动是在恒定方向上以恒定速度移动。
输入
第一行包含一个整数 $$$N$$$ ($$$2 \leq N \leq 100\,000$$$) 表示我们捕获两个朋友位置的时刻数。
第二行包含两个整数 $$$d_1$$$ 和 $$$d_2 \ (0 < d_1 < d_2 < 1000)$$$。
接下来的 $$$N$$$ 行包含四个整数 $$$A_x,A_y,B_x,B_y$$$ ($$$0 \leq A_x, A_y, B_x, B_y \leq 1000$$$) 代表朋友 A 和 B 在每个捕获时刻的坐标。
输出
输出包含一个整数,表示朋友会说“Hello!”的次数彼此。
示例
输入 #1
4 2 5 0 0 0 10 5 5 5 6 5 0 10 5 14 7 10 5
输出 #1
2
注意
解释:朋友应该互相发送信号 2 次,第一次是在点 $$$A2$$$ 和 $$$B2$$$ 附近,第二次是在 A 从 $$$A3$$$ 到 $$$A4$$$ 的行程中,而 B 停留在 $$$B3=B4$$$ 点。