{"problem":{"name":"E. Contact ATC","description":{"content":"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 eno","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF957E"},"statements":[{"statement_type":"Markdown","content":"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.\n\nOccasionally, 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_.\n\nAccording 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.\n\nEach 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.\n\nThe wind speed is the same for all planes. You may assume that the wind has a steady speed and lasts arbitrarily long.\n\n## Input\n\nThe first line contains two integers _n_ and _w_ (1 ≤ _n_ ≤ 100 000, 0 ≤ _w_ < 105) — the number of planes and the maximum wind speed.\n\nThe _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.\n\nPlanes 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\n## Output\n\nOutput a single integer — the number of unordered pairs of planes that can contact Arkady at the same moment.\n\n[samples]\n\n## Note\n\nIn the first example, the following 3 pairs of planes satisfy the requirements:\n\n*   **(2, 5)** passes the station at time 3 / 4 with _v__wind_ = 1;\n*   **(3, 4)** passes the station at time 2 / 5 with _v__wind_ = 1 / 2;\n*   **(3, 5)** passes the station at time 4 / 7 with _v__wind_ =  - 1 / 4.\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Arkady 是空中交通管制员，目前正在管理 #cf_span[n] 架飞机。所有飞机沿一条直线坐标轴飞行，Arkady 的站点位于点 #cf_span[0]。第 #cf_span[i] 架飞机（可视为一个点）当前位于坐标 #cf_span[xi]，并以速度 #cf_span[vi] 移动。保证 #cf_span[xi·vi < 0]，即所有飞机均朝向站点飞行。\n\n偶尔，飞机受风影响。当风速为 #cf_span[vwind]（不一定是正数或整数）时，第 #cf_span[i] 架飞机的速度变为 #cf_span[vi + vwind]。\n\n根据天气报告，当前风速稳定且落在范围 #cf_span[[ - w, w]]（包含端点）内，但由于该值较小——小于任何飞机速度的绝对值——无法精确测量。\n\n每架飞机应在恰好经过站点上方时与 Arkady 联系。你需要帮助 Arkady 计算满足以下条件的无序飞机对 #cf_span[(i, j)]（#cf_span[i < j]）的数量：存在某个风速值，使得飞机 #cf_span[i] 和 #cf_span[j] 在同一时刻与 Arkady 联系。不同对的风速值可以不同。\n\n风速对所有飞机相同。你可以假设风速恒定且持续时间任意长。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[w]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[0 ≤ w < 105]）——飞机数量和最大风速。\n\n接下来的 #cf_span[n] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[vi]（#cf_span[1 ≤ |xi| ≤ 105]，#cf_span[w + 1 ≤ |vi| ≤ 105]，#cf_span[xi·vi < 0]）——第 #cf_span[i] 架飞机的初始位置和速度。\n\n所有飞机互不相同，即不存在满足 #cf_span[xi = xj] 且 #cf_span[vi = vj] 的不同对 #cf_span[(i, j)]（#cf_span[i < j]）。\n\n请输出一个整数——能够同时与 Arkady 联系的无序飞机对的数量。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[w]（#cf_span[1 ≤ n ≤ 100 000]，#cf_span[0 ≤ w < 105]）——飞机数量和最大风速。第 #cf_span[i] 行包含两个整数 #cf_span[xi] 和 #cf_span[vi]（#cf_span[1 ≤ |xi| ≤ 105]，#cf_span[w + 1 ≤ |vi| ≤ 105]，#cf_span[xi·vi < 0]）——第 #cf_span[i] 架飞机的初始位置和速度。所有飞机互不相同，即不存在满足 #cf_span[xi = xj] 且 #cf_span[vi = vj] 的不同对 #cf_span[(i, j)]（#cf_span[i < j]）。\n\n## Output\n\n输出一个整数——能够同时与 Arkady 联系的无序飞机对的数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，以下 #cf_span[3] 对飞机满足要求：\n*#cf_span[(2, 5)]* 在风速 #cf_span[vwind = 1] 时于时间 #cf_span[3 / 4] 经过站点；\n*#cf_span[(3, 4)]* 在风速 #cf_span[vwind = 1 / 2] 时于时间 #cf_span[2 / 5] 经过站点；\n*#cf_span[(3, 5)]* 在风速 #cf_span[vwind =  - 1 / 4] 时于时间 #cf_span[4 / 7] 经过站点。\n\n在第二个例子中，三个坐标为负的飞机中的每一个都可以与另外三个飞机中的每一个组成有效对，共计 #cf_span[9] 对。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of planes, and $ w \\geq 0 $ the maximum wind speed magnitude. For each plane $ i $, let $ x_i \\in \\mathbb{R} \\setminus \\{0\\} $ be its initial position and $ v_i \\in \\mathbb{R} \\setminus \\{0\\} $ its initial speed, with $ x_i v_i < 0 $ (i.e., all planes are moving toward the origin).\n\nThe wind speed $ v_{\\text{wind}} \\in [-w, w] $ is uniform across all planes. The effective speed of plane $ i $ under wind is $ v_i + v_{\\text{wind}} $.\n\nPlane $ i $ reaches the station (origin) at time:\n$$\nt_i = \\frac{-x_i}{v_i + v_{\\text{wind}}}\n$$\nsince $ x_i v_i < 0 $, the denominator is nonzero and the time is positive.\n\nWe are to count the number of unordered pairs $ (i, j) $ with $ i < j $ such that there exists some $ v_{\\text{wind}} \\in [-w, w] $ for which:\n$$\nt_i = t_j \\quad \\Longleftrightarrow \\quad \\frac{-x_i}{v_i + v_{\\text{wind}}} = \\frac{-x_j}{v_j + v_{\\text{wind}}}\n$$\n\nThis simplifies to:\n$$\n\\frac{x_i}{v_i + v_{\\text{wind}}} = \\frac{x_j}{v_j + v_{\\text{wind}}}\n$$\n\nCross-multiplying:\n$$\nx_i (v_j + v_{\\text{wind}}) = x_j (v_i + v_{\\text{wind}})\n$$\n\nExpanding:\n$$\nx_i v_j + x_i v_{\\text{wind}} = x_j v_i + x_j v_{\\text{wind}}\n$$\n\nRearranging:\n$$\nx_i v_j - x_j v_i = v_{\\text{wind}} (x_j - x_i)\n$$\n\nSolving for $ v_{\\text{wind}} $:\n$$\nv_{\\text{wind}} = \\frac{x_i v_j - x_j v_i}{x_j - x_i}\n$$\n\nNote: $ x_j - x_i \\neq 0 $ since all planes are distinct and $ x_i v_i < 0 $ implies no two planes can have same position and speed (given), and if $ x_i = x_j $, then since $ x_i v_i < 0 $, $ v_i $ and $ v_j $ must have same sign, but then $ x_i v_j - x_j v_i = x_i (v_j - v_i) \\neq 0 $ unless $ v_i = v_j $, which is disallowed. So $ x_i \\ne x_j $ always.\n\nThus, for each pair $ (i, j) $, define:\n$$\nv_{ij} = \\frac{x_i v_j - x_j v_i}{x_j - x_i}\n$$\n\nWe count the number of unordered pairs $ (i, j) $, $ i < j $, such that:\n$$\nv_{ij} \\in [-w, w]\n$$\n\nThis is the final condition.\n\n---\n\n**Formal Statement:**\n\nGiven:\n- $ n \\in \\mathbb{N} $, $ w \\in \\mathbb{R}_{\\geq 0} $\n- For $ i = 1, \\dots, n $: $ x_i \\in \\mathbb{R} \\setminus \\{0\\} $, $ v_i \\in \\mathbb{R} \\setminus \\{0\\} $, with $ x_i v_i < 0 $, and all $ (x_i, v_i) $ distinct.\n\nDefine for each pair $ (i, j) $, $ i < j $:\n$$\nv_{ij} = \\frac{x_i v_j - x_j v_i}{x_j - x_i}\n$$\n\nCount:\n$$\n\\left| \\left\\{ (i, j) \\mid 1 \\leq i < j \\leq n,\\; v_{ij} \\in [-w, w] \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF957E","tags":[],"sample_group":[["5 1\n-3 2\n-3 3\n-1 2\n1 -3\n3 -5","3"],["6 1\n-3 2\n-2 2\n-1 2\n1 -2\n2 -2\n3 -2","9"]],"created_at":"2026-03-03 11:00:39"}}