Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1.5 s 空间限制:256 MB

#4363. 「VK Cup 2018 Round 2」联系管理员

Statistics

题目描述

空中交通管理员阿尔卡狄现在正要接管空中的 $n$ 架飞机。所有的飞机都在一条直坐标轴上,阿尔卡狄所在的控制中心处于坐标 $0$。第 $i$ 架飞机目前处于坐标 $x_i$(飞机本身的大小可忽略),以 $v_i$ 的速度移动,其中 $w_i \cdot v_i < 0$,即所有飞机都正面向控制中心移动。

飞机的速度会被气流影响。在速度为 $u$ 的气流中,第 $i$ 架飞机的速度变为 $v_i + u$。

按照气象报告,目前气流的速度是处于 $[-w, w]$ 范围内的一个实数,但是确切值无法测量,因为这个值太小了,小于任何一架飞机的速率 —— 也就是说 $|w| < v_i\ \forall i$。

每一架飞机在经过控制中心的时刻都需要与阿尔卡狄进行通信。

请帮助阿尔卡狄计算这样的整数对 $(i, j)$($i < j$)使得存在一个 $[-w, w]$ 范围内的气流速度使第 $i$ 架和第 $j$ 架飞机同时与阿尔卡狄进行通信。这个速度对于不同的整数对可以不同,并且气流持续的时间足够长。

输入格式

输入的第一行包含两个空格分隔的整数 $n$,$w$ —— 飞机的数量和气流的最大速率。

接下来 $n$ 行每行包含两个空格分隔的整数 $x_i$ 和 $v_i$ —— 第 $i$ 架飞机的初始坐标和初始速度。

飞机两两不同,即不存在整数对 $(i, j)$($i \neq j$)使得 $x_i = x_j$ 且 $v_i = v_j$。

输出格式

输出一行,包含一个整数,表示可能同时联系阿尔卡狄的飞机对数。

样例 1

input

5 1
-3 2
-3 3
-1 2
1 -3
3 -5

output

3

样例 1 中,下列三对飞机满足条件:

  • $(2, 5)$ 在气流速度为 $1$ 时,于时刻 $\frac 3 4$ 同时经过控制中心;
  • $(3, 4)$ 在气流速度为 $\frac 1 2$ 时,于时刻 $\frac 2 5$ 同时经过控制中心;
  • $(3, 5)$ 在气流速度为 $-\frac 1 4$ 时,于时刻 $\frac 4 7$ 同时经过控制中心。

样例 2

input

6 1
-3 2
-2 2
-1 2
1 -2
2 -2
3 -2

output

9

样例 2 中,每架负坐标的飞机和每架正坐标的飞机都可能同时联系阿尔卡狄,因此答案为 $3 \times 3 = 9$。

数据范围与提示

$1 \leq n \leq 10^5$
$0 \leq w \lt 10^5$
$1 \leq |x_i| \leq 10^5$,$w + 1 \leq |v_i| \leq 10^5$,$x_i \cdot v_i < 0$