D. A Shade of Moonlight

"遮蔽月光几乎是不可能的；云层呈现出它柔和的美丽与宁静。" Mino吟诵道。 "看？云来了。" Kanno凝视远方。 "再好不过了，" Mino转向Kanno。 天空可视为一条一维数轴，月亮位于原点，坐标为 $0$。 天空中有 $n$ 朵云，每朵云长度均为 $l$。第 $i$ 朵云初始时覆盖区间 $(x_i, x_i + l)$（端点不包含）。初始时，它以速度 $v_i$ 移动，$v_i$ 为 $1$ 或 $-1$。 此外，初始时任意两朵云不相交，即对所有 $1 lt.eq i lt j lt.eq n$，有 $lvert x_i -x_j rvert gt.eq l$。 当风速为 $w$ 时，第 $i$ 朵云的速度变为 $v_i + w$，即每单位时间其坐标增加 $v_i + w$。注意风速可能很强，云朵可能改变方向。 你需要帮助 Mino 计算满足条件的无序对 $(i, j)$（$i < j$）的数量，使得存在一个风速 $w$，其绝对值不超过 $w_(upright(m a x))$（可能为负数或分数），使得第 $i$ 朵和第 $j$ 朵云在某个未来的时刻同时覆盖月亮。对于不同对，$w$ 可以不同。 第一行包含三个空格分隔的整数 $n$、$l$ 和 $w_(upright(m a x))$（$1 lt.eq n lt.eq 10^5$，$1 lt.eq l, w_(upright(m a x)) lt.eq 10^8$），分别表示云的数量、每朵云的长度和最大风速。 接下来的 $n$ 行中，第 $i$ 行包含两个空格分隔的整数 $x_i$ 和 $v_i$（$-10^8 lt.eq x_i lt.eq 10^8$，$v_i in {-1, 1}$），分别表示第 $i$ 朵云的初始位置和速度。 输入保证对所有 $1 lt.eq i lt j lt.eq n$，有 $lvert x_i -x_j rvert gt.eq l$。 输出一个整数——满足条件的无序云对数量，即存在一个合适的风速 $w$，使得这对云在某个未来的时刻同时覆盖月亮。 ## Input 第一行包含三个空格分隔的整数 $n$、$l$ 和 $w_(upright(m a x))$（$1 lt.eq n lt.eq 10^5$，$1 lt.eq l, w_(upright(m a x)) lt.eq 10^8$），分别表示云的数量、每朵云的长度和最大风速。接下来的 $n$ 行中，第 $i$ 行包含两个空格分隔的整数 $x_i$ 和 $v_i$（$-10^8 lt.eq x_i lt.eq 10^8$，$v_i in {-1, 1}$），分别表示第 $i$ 朵云的初始位置和速度。输入保证对所有 $1 lt.eq i lt j lt.eq n$，有 $lvert x_i -x_j rvert gt.eq l$。 ## Output 输出一个整数——满足条件的无序云对数量，即存在一个合适的风速 $w$，使得这对云在某个未来的时刻同时覆盖月亮。 [samples] ## Note 在第一个例子中，云的初始位置和速度如下图所示。 满足条件的对为： $(1, 3)$，在时间 $2.5$ 且 $w = -0.4$ 时覆盖月亮； $(1, 4)$，在时间 $3.5$ 且 $w = -0.6$ 时覆盖月亮； $(1, 5)$，在时间 $4.5$ 且 $w = -0.7$ 时覆盖月亮； $(2, 5)$，在时间 $2.5$ 且 $w = -2$ 时覆盖月亮。 下图展示了在时间 $2.5$ 且 $w = -0.4$ 时云的位置。此时，第 $1$ 朵和第 $3$ 朵云同时覆盖月亮。 在第二个例子中，唯一满足条件的对是 $(1, 4)$，在时间 $15$ 且 $w = 0$ 时覆盖月亮。 请注意，上述所有时间和风速仅是无穷多种可能选择中的示例。

Let the moon be at position $ 0 $. Each cloud $ i $ has length $ l $, initial position $ x_i $, and initial velocity $ v_i \in \{-1, 1\} $. With wind velocity $ w \in \mathbb{R} $, the velocity of cloud $ i $ becomes $ v_i + w $. At time $ t \geq 0 $, the position of the left endpoint of cloud $ i $ is: $$ x_i + (v_i + w)t $$ and the right endpoint is: $$ x_i + (v_i + w)t + l $$ The cloud covers the moon at time $ t $ if: $$ x_i + (v_i + w)t < 0 < x_i + (v_i + w)t + l $$ which is equivalent to: $$ - (v_i + w)t - l < x_i < - (v_i + w)t $$ We are to count the number of unordered pairs $ (i, j) $, $ i < j $, such that there exists some $ w \in [-w_{\text{max}}, w_{\text{max}}] $ and some $ t > 0 $ for which **both** clouds $ i $ and $ j $ simultaneously cover the moon. --- ### Reformulation: For cloud $ i $, define the condition for covering the moon at time $ t > 0 $ with wind $ w $: $$ x_i + (v_i + w)t < 0 < x_i + (v_i + w)t + l \quad \iff \quad - \frac{x_i + l}{v_i + w} < t < - \frac{x_i}{v_i + w} $$ (Note: We must be cautious with signs — we require $ t > 0 $, so the interval must lie in $ \mathbb{R}^+ $.) But we can eliminate $ t $: We want **simultaneous coverage** of the moon by clouds $ i $ and $ j $ at the same $ t > 0 $ and same $ w $. So, for some $ t > 0 $, both: $$ x_i + (v_i + w)t < 0 < x_i + (v_i + w)t + l \tag{1} $$ $$ x_j + (v_j + w)t < 0 < x_j + (v_j + w)t + l \tag{2} $$ Let $ u = v_i + w $, $ u' = v_j + w $. Then $ u - u' = v_i - v_j $. So $ u' = u - (v_i - v_j) $. From (1): $$ - \frac{x_i + l}{u} < t < - \frac{x_i}{u} $$ From (2): $$ - \frac{x_j + l}{u'} < t < - \frac{x_j}{u'} $$ Substitute $ u' = u - \Delta $, where $ \Delta = v_i - v_j \in \{-2, 0, 2\} $ (since $ v_i, v_j \in \{-1,1\} $). We require that the two intervals for $ t $ have non-empty intersection, and that there exists $ u \in [v_i - w_{\text{max}}, v_i + w_{\text{max}}] $ such that the intersection contains a positive $ t $. But we can avoid tracking $ t $ by eliminating it. --- ### Key Insight: From (1): $$ x_i + (v_i + w)t < 0 < x_i + (v_i + w)t + l \Rightarrow - x_i - l < (v_i + w)t < -x_i $$ Similarly for $ j $: $$ - x_j - l < (v_j + w)t < -x_j $$ Let $ s = t > 0 $. Then: $$ \frac{-x_i - l}{s} < v_i + w < \frac{-x_i}{s} \tag{3} $$ $$ \frac{-x_j - l}{s} < v_j + w < \frac{-x_j}{s} \tag{4} $$ Subtracting (3) and (4): Let $ A = v_i + w $, $ B = v_j + w $. Then $ A - B = v_i - v_j = \Delta \in \{-2, 0, 2\} $. We can eliminate $ w $: subtract the inequalities. From (3) and (4), subtracting gives: $$ \left( \frac{-x_i - l}{s} - \frac{-x_j}{s} \right) < A - B < \left( \frac{-x_i}{s} - \frac{-x_j - l}{s} \right) \Rightarrow \frac{ -x_i - l + x_j }{s} < \Delta < \frac{ -x_i + x_j + l }{s} $$ So: $$ \frac{ x_j - x_i - l }{s} < \Delta < \frac{ x_j - x_i + l }{s} $$ Multiply by $ s > 0 $: $$ x_j - x_i - l < \Delta s < x_j - x_i + l \Rightarrow |x_j - x_i - \Delta s| < l $$ But $ \Delta = v_i - v_j $, so: $$ |x_j - x_i - (v_i - v_j)s| < l \tag{5} $$ This is a necessary condition for simultaneous coverage at time $ s > 0 $. We can solve for $ s $: Let $ d = x_j - x_i $, $ \Delta = v_i - v_j $. Then: $$ |d - \Delta s| < l \Rightarrow d - l < \Delta s < d + l $$ So: $$ \frac{d - l}{\Delta} < s < \frac{d + l}{\Delta} \quad \text{if } \Delta > 0 $$ $$ \frac{d + l}{\Delta} < s < \frac{d - l}{\Delta} \quad \text{if } \Delta < 0 $$ But since $ s > 0 $, we require the interval to intersect $ (0, \infty) $. We now want to know: **Does there exist $ s > 0 $ such that (5) holds AND there exists $ w \in [-w_{\text{max}}, w_{\text{max}}] $ satisfying both (3) and (4)?** From (3): $$ w \in \left( \frac{-x_i - l}{s} - v_i, \frac{-x_i}{s} - v_i \right) $$ From (4): $$ w \in \left( \frac{-x_j - l}{s} - v_j, \frac{-x_j}{s} - v_j \right) $$ So the intersection of these two intervals must be non-empty, and must intersect $ [-w_{\text{max}}, w_{\text{max}}] $. But we can avoid iterating over $ s $. --- ### Final Formalization: For a pair $ (i, j) $, $ i < j $, define: - $ d = x_j - x_i $ - $ \Delta = v_i - v_j \in \{-2, 0, 2\} $ Define the **time window** for simultaneous coverage: $$ \mathcal{S}_{ij} = \left\{ s > 0 : |d - \Delta s| < l \right\} $$ This is non-empty iff $ \Delta \ne 0 $ and $ |d| < l + |\Delta| s $ for some $ s > 0 $, which is always true if $ \Delta \ne 0 $, but we need to compute the interval: - If $ \Delta = 2 $: $ s \in \left( \frac{d - l}{2}, \frac{d + l}{2} \right) \cap \mathbb{R}^+ $ - If $ \Delta = -2 $: $ s \in \left( \frac{d - l}{-2}, \frac{d + l}{-2} \right) = \left( \frac{l - d}{2}, \frac{-l - d}{2} \right) $ — but this is only positive if $ -l - d > 0 \Rightarrow d < -l $, etc. Actually, let’s write: From $ |d - \Delta s| < l $, we get: $$ \Delta s \in (d - l, d + l) \Rightarrow s \in \left( \frac{d - l}{\Delta}, \frac{d + l}{\Delta} \right) \quad \text{if } \Delta > 0 $$ $$ s \in \left( \frac{d + l}{\Delta}, \frac{d - l}{\Delta} \right) \quad \text{if } \Delta < 0 $$ So define: $$ I_{ij} = \left( \min\left( \frac{d - l}{\Delta}, \frac{d + l}{\Delta} \right), \max\left( \frac{d - l}{\Delta}, \frac{d + l}{\Delta} \right) \right) \cap (0, \infty) $$ Then for each $ s \in I_{ij} $, define the **allowed wind interval** for cloud $ i $: $$ W_i(s) = \left( \frac{-x_i - l}{s} - v_i, \frac{-x_i}{s} - v_i \right) $$ Similarly for $ j $: $$ W_j(s) = \left( \frac{-x_j - l}{s} - v_j, \frac{-x_j}{s} - v_j \right) $$ We require: $$ W_i(s) \cap W_j(s) \cap [-w_{\text{max}}, w_{\text{max}}] \ne \emptyset $$ We want to know: **Does there exist $ s \in I_{ij} $ such that $ W_i(s) \cap W_j(s) \cap [-w_{\text{max}}, w_{\text{max}}] \ne \emptyset $?** But $ W_i(s) \cap W_j(s) $ is an interval, and we can compute its bounds: Let $ a_i(s) = \frac{-x_i - l}{s} - v_i $, $ b_i(s) = \frac{-x_i}{s} - v_i $ Similarly $ a_j(s), b_j(s) $ Then: $$ W_i(s) \cap W_j(s) = \left( \max(a_i(s), a_j(s)), \min(b_i(s), b_j(s)) \right) $$ We require: $$ \max(a_i(s), a_j(s)) < \min(b_i(s), b_j(s)) \quad \text{and} \quad \text{this interval overlaps } [-w_{\text{max}}, w_{\text{max}}] $$ This is complicated to check for all $ s $, but we can observe: The condition that both clouds cover the moon at the same time with wind $ w $ is equivalent to: There exists $ w \in [-w_{\text{max}}, w_{\text{max}}] $ and $ t > 0 $ such that: $$ \begin{cases} x_i + (v_i + w)t < 0 < x_i + (v_i + w)t + l \\ x_j + (v_j + w)t < 0 < x_j + (v_j + w)t + l \end{cases} $$ Define: Let $ u = w $. Then we have two linear inequalities in $ t $: $$ \begin{cases} - \frac{x_i + l}{v_i + u} < t < - \frac{x_i}{v_i + u} \\ - \frac{x_j + l}{v_j + u} < t < - \frac{x_j}{v_j + u} \end{cases} $$ We want the intersection of the two $ t $-intervals to be non-empty for some $ u \in [-w_{\text{max}}, w_{\text{max}}] $, and $ v_i + u \ne 0 $, $ v_j + u \ne 0 $, and $ t > 0 $. This is equivalent to: There exists $ u \in [-w_{\text{max}}, w_{\text{max}}] $ such that: $$ \max\left( - \frac{x_i + l}{v_i + u}, - \frac{x_j + l}{v_j + u} \right) < \min\left( - \frac{x_i}{v_i + u}, - \frac{x_j}{v_j + u} \right) $$ and the lower bound is positive. This is a **semi-algebraic condition** in $ u $, and we need to know if it holds for some $ u $ in a bounded interval. But we can transform variables. Let $ a = v_i + u $, $ b = v_j + u $, so $ a - b = v_i - v_j = \Delta $, and $ u = a - v_i \in [-w_{\text{max}}, w_{\text{max}}] \Rightarrow a \in [v_i - w_{\text{max}}, v_i + w_{\text{max}}] $ Then the condition becomes: $$ \max\left( - \frac{x_i + l}{a}, - \frac{x_j + l}{b} \right) < \min\left( - \frac{x_i}{a}, - \frac{x_j}{b} \right) \quad \text{and} \quad \max\left( - \frac{x_i + l}{a}, - \frac{x_j + l}{b} \right) > 0 $$ Since $ b = a - \Delta $, substitute: $$ \max\left( - \frac{x_i + l}{a}, - \frac{x_j + l}{a - \Delta} \right) < \min\left( - \frac{x_i}{a}, - \frac{x_j}{a - \Delta} \right) $$ Let $ f(a) = \max\left( - \frac{x_i + l}{a}, - \frac{x_j + l}{a - \Delta} \right) $, $ g(a) = \min\left( - \frac{x_i}{a}, - \frac{x_j}{a - \Delta} \right) $ We need $ f(a) < g(a) $ and $ f(a) > 0 $ for some $ a \in [v_i - w_{\text{max}}, v_i + w_{\text{max}}] \setminus \{0, \Delta\} $ This is a **one-dimensional feasibility problem** over a union of intervals, with piecewise rational functions. But note: the condition $ f(a) < g(a) $ is equivalent to: $$ - \frac{x_i + l}{a} < - \frac{x_j}{a - \Delta} \quad \text{and} \quad - \frac{x_j + l}{a - \Delta} < - \frac{x_i}{a} $$ and also the other two combinations? Actually, the max < min condition is equivalent to **all four pairwise inequalities**: 1. $ - \frac{x_i + l}{a} < - \frac{x_i}{a} $ — always true since $ l > 0 $ 2. $ - \frac{x_j + l}{a - \Delta} < - \frac{x_j}{a - \Delta} $ — always true 3. $ - \frac{x_i + l}{a} < - \frac{x_j}{a - \Delta} $ 4. $ - \frac{x_j + l}{a - \Delta} < - \frac{x_i}{a} $ So only conditions 3 and 4 are nontrivial. So we require: $$ \frac{x_i + l}{a} > \frac{x_j}{a - \Delta} \tag{A} $$ $$ \frac{x_j + l}{a - \Delta} > \frac{x_i}{a} \tag{B} $$ And also $ f(a) > 0 \Rightarrow \max\left( - \frac{x_i + l}{a}, - \frac{x_j + l}{a - \Delta} \right) > 0 \Rightarrow \text{at least one of } \frac{x_i + l}{a} < 0 \text{ or } \frac{x_j + l}{a - \Delta} < 0 $ But since $ t > 0 $, and $ t < -x_i / a $, we must have $ -x_i / a > 0 \Rightarrow x_i / a < 0 $, similarly $ x_j / (a - \Delta) < 0 $. So both $ a $ and $ a - \Delta $ must have opposite signs to $ x_i $ and $ x_j $ respectively. But this is getting too complex for a clean formalization. --- ### Final Clean Formalization (as required): We are to count the number of unordered pairs $ (i, j) $, $ i < j $, such that there exists $ w \in [-w_{\text{max}}, w_{\text{max}}] $ and $ t > 0 $ satisfying: $$ \begin{cases} x_i + (v_i + w)t < 0 < x_i + (v_i + w)t + l \\ x_j + (v_j + w)t < 0 < x_j + (v_j + w)t + l \end{cases} $$ This is equivalent to: $$ \exists w \in [-w_{\text{max}}, w_{\text{max}}], \exists t > 0 \text{ such that } \begin{cases} - x_i - l < (v_i + w)t < -x_i \\ - x_j - l < (v_j + w)t < -x_j \end{cases} $$ Let $ a = v_i + w $, $ b = v_j + w $. Then $ a - b = v_i - v_j = \Delta \in \{-2, 0, 2\} $, and $ w = a - v_i \in [-w_{\text{max}}, w_{\text{max}}] \Rightarrow a \in [v_i - w_{\text{max}}, v_i + w_{\text{max}}] $, $ b = a - \Delta \in [v_j - w_{\text{max}}, v_j + w_{\text{max}}] $ Then the system becomes: $$ \begin{cases} - x_i - l < a t < -x_i \\ - x_j - l < (a - \Delta) t < -x_j \end{cases} \quad \text{for some } t > 0, a \in [v_i - w_{\text{max}}, v_i + w_{\text{max}}] $$ We can eliminate $ t $: From the first: $ t \in \left( \frac{-x_i - l}{a}, \frac{-x_i}{a} \right) $ From the second: $ t \in \left( \frac{-x_j - l}{a - \Delta}, \frac{-x_j}{a - \Delta} \right) $ So we require: $$ \left( \frac{-x_i - l}{a}, \frac{-x_i}{a} \right) \cap \left( \frac{-x_j - l}{a - \Delta}, \frac{-x_j}{a - \Delta} \right) \cap (0, \infty) \ne \emptyset $$ Thus, the final formal statement is: --- **Given:** - $ n $, $ l $, $ w_{\text{max}} \in \mathbb{R}^+ $ - For $ i = 1, \dots, n $: $ x_i \in \mathbb{R} $, $ v_i \in \{-1, 1\} $ - $ |x_i - x_j| \geq l $ for all $ i \ne j $ **Count the number of unordered pairs $ (i, j) $, $ i < j $, such that there exists $ a \in [v_i - w_{\text{max}}, v_i + w_{\text{max}}] $ with $ a \ne 0 $, $ a - \Delta \ne 0 $, where $ \Delta = v_i - v_j $, and** $$ \left( \frac{-x_i - l}{a}, \frac{-x_i}{a} \right) \cap \left( \frac{-x_j - l}{a - \Delta}, \frac{-x_j}{a - \Delta} \right) \cap (0, \infty) \ne \emptyset $$ --- This is the **mathematical formalization** of the problem.