CF924D.Contact ATC
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Arkady the air traffic controller is now working with n planes in the air. All planes move along a straight coordinate axis with Arkady's station being at point 0 on it. The i-th plane, small enough to be represented by a point, currently has a coordinate of x__i and is moving with speed v__i. It's guaranteed that x__i·v__i < 0, i.e., all planes are moving towards the station.
Occasionally, the planes are affected by winds. With a wind of speed v__wind (not necessarily positive or integral), the speed of the i-th plane becomes v__i + v__wind.
According to weather report, the current wind has a steady speed falling inside the range [ - w, w] (inclusive), but the exact value cannot be measured accurately since this value is rather small — smaller than the absolute value of speed of any plane.
Each plane should contact Arkady at the exact moment it passes above his station. And you are to help Arkady count the number of pairs of planes (i, j) (i < j) there are such that there is a possible value of wind speed, under which planes i and j contact Arkady at the same moment. This value needn't be the same across different pairs.
The wind speed is the same for all planes. You may assume that the wind has a steady speed and lasts arbitrarily long.
空中交通管制员阿尔卡季目前正在管理空中的 n 架飞机。所有飞机均沿一条直线坐标轴飞行,阿尔卡季所在的管制站位于该轴上的原点 0 处。第 i 架飞机体积足够小,可视为一个质点,当前坐标为 xi,飞行速度为 vi。已知 xi⋅vi<0,即所有飞机均正朝向管制站飞行。
偶尔,飞机会受到风的影响。当风速为 vwind(该值不一定是正数,也不一定是整数)时,第 i 架飞机的实际速度变为 vi+vwind。
根据天气预报,当前风速稳定且取值范围为 [−w,w](闭区间),但其精确值无法被准确测量,因为该值非常小——其绝对值小于任意一架飞机速度的绝对值。
每架飞机必须在恰好飞越管制站上空的时刻与阿尔卡季取得联系。你需要帮助阿尔卡季计算满足如下条件的飞机对 (i,j)(其中 i<j)的数目:存在某个可能的风速值,使得飞机 i 和飞机 j 恰好在同一时刻与阿尔卡季联系。不同飞机对所对应的风速值可以不同。
风速对所有飞机是相同的。你可以假设风速恒定且持续时间足够长。
输入格式
The first line contains two integers n and w (1 ≤ n ≤ 100 000, 0 ≤ w < 105) — the number of planes and the maximum wind speed.
The i-th of the next n lines contains two integers x__i and v__i (1 ≤ |x__i| ≤ 105, w + 1 ≤ |v__i| ≤ 105, x__i·v__i < 0) — the initial position and speed of the i-th plane.
Planes are pairwise distinct, that is, no pair of (i, j) (i < j) exists such that both x__i = x__j and v__i = v__j.
第一行包含两个整数 n 和 w(1 ≤ n ≤ 100000,0 ≤ w < 105)—— 分别表示飞机的数量和最大风速。
接下来的 n 行中,第 i 行包含两个整数 xi 和 vi(1 ≤ ∣xi∣ ≤ 105,w + 1 ≤ ∣vi∣ ≤ 105,且 xi⋅vi < 0)—— 表示第 i 架飞机的初始位置和速度。
所有飞机互不相同,即不存在满足 i<j 且同时有 xi=xj 与 vi=vj 的飞机对 (i, j)。
输出格式
Output a single integer — the number of unordered pairs of planes that can contact Arkady at the same moment.
输出一个整数——能够同时与 Arkady 取得联系的无序平面对的数量。
输入输出样例
输入#1
5 1 -3 2 -3 3 -1 2 1 -3 3 -5
输出#1
3
输入#2
6 1 -3 2 -2 2 -1 2 1 -2 2 -2 3 -2
输出#2
9
说明/提示
In the first example, the following 3 pairs of planes satisfy the requirements:
- (2, 5) passes the station at time 3 / 4 with v__wind = 1;
- (3, 4) passes the station at time 2 / 5 with v__wind = 1 / 2;
- (3, 5) passes the station at time 4 / 7 with v__wind = - 1 / 4.
In the second example, each of the 3 planes with negative coordinates can form a valid pair with each of the other 3, totaling 9 pairs.
在第一个例子中,以下 3 对飞机满足要求:
- (2, 5) 在时刻 3/4 经过观测站,此时 vwind=1;
- (3, 4) 在时刻 2/5 经过观测站,此时 vwind=1/2;
- (3, 5) 在时刻 4/7 经过观测站,此时 vwind=−1/4。
在第二个例子中,每架坐标为负的飞机均可与其余 3 架飞机中的任意一架组成合法对,共形成 9 对。
输入解题思路,AI测评打分。不知道怎么写?