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

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

题目描述

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

飞机的速度会被气流影响。在速度为 uu 的气流中,第 ii 架飞机的速度变为 vi+uv_i + u

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

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

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

输入格式

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

接下来 nn 行每行包含两个空格分隔的整数 xix_iviv_i —— 第 ii 架飞机的初始坐标和初始速度。

飞机两两不同,即不存在整数对 (i,j)(i, j)iji \neq j)使得 xi=xjx_i = x_jvi=vjv_i = v_j

输出格式

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

5 1
-3 2
-3 3
-1 2
1 -3
3 -5
3
6 1
-3 2
-2 2
-1 2
1 -2
2 -2
3 -2
9

数据范围与提示

1n1051 \leq n \leq 10^5
0w<1050 \leq w \lt 10^5
1xi1051 \leq |x_i| \leq 10^5w+1vi105w + 1 \leq |v_i| \leq 10^5xivi<0x_i \cdot v_i < 0