题解：P17126 [ICPC 2025 Shanghai R] Flower' s land 4

failedzroge · 2026-07-24 00:58:39 · 题解

计算几何加李超树好题。题目给出了 n 条形如 \frac{X}{x_i}+\frac{Y}{y_i}=1 的线段，再给了 q 次询问，每次问端点 P(a_i,0),Q(b_i,c_i) 构成的线段是否和已有的线段相交。

由于所有线段均在第一象限，且 P 点位于 X 轴上，若它和某条线段相交，则要么 P 位于线段下方，Q 位于上方，要么反过来。两种情况我们可以分开判断。考虑 P(a,0) 在某条线段下方的情景。因为给定的线段是完整卡住第一象限的，故 P 位于线段下方的条件等价于 a<x_i，这引导我们思考扫描线。

我们将所有给定的线段和询问按 x 排序， 并按从大到小的顺序将线段插入李超树，并维护各段区间最小值。处理询问时，由于我们钦定了已有的线段都在 P 上方，所以只需要查询 Q 点的 y 坐标是否在该区间处超过李超树的最小值即可。

对于 P 在上方的情况我们从小到大排序，并用李超树维护最大值即可。注意需要特判线段 x_i=0 或者 y_i=0 的情况。总时间复杂度为 O(n\log n)，可以通过本题。