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

lailai0916 · 2026-08-31 02:58:16 · 题解

题意简述

给定若干连接非负 x 轴与非负 y 轴的线段。 每次询问给出一条从 x 轴出发、终点位于第一象限或坐标轴上的线段。 判断它是否与任意给定线段相交，端点相交也算。

解题思路

先只考虑 x_i>0 且 y_i>0 的给定线段。 它连接 (x_i,0) 与 (0,y_i)，所在直线在横坐标 z 处的高度为：

这条直线在第一象限中的部分恰好是给定线段。 询问线段的两个端点都在第一象限或边界上。 因此，它与给定线段相交， 当且仅当两个询问端点位于该直线两侧，或至少一个端点在直线上。 交点仍在第一象限内，所以一定落在给定线段上。

询问起点为 (a,0)。 若 a\le x_i，起点位于直线下方或线上。 此时询问终点 (b,c) 必须位于直线上方或线上，即：

于是第一类相交条件为：

若 a\ge x_i，起点位于直线上方或线上， 终点必须位于直线下方或线上，即 h_i(b)\ge c。 第二类相交条件为：

当 a=x_i 时，询问起点就是给定线段的端点。 两个条件都允许等号， 而任意实数都满足不大于或不小于 c 中的至少一个， 所以端点相交不会被遗漏。

把给定线段按 x_i 排序，把询问按 a 排序。 从大到小扫描询问时，逐步加入所有 x_i\ge a 的直线， 维护它们在横坐标 b 处的最小高度。 从小到大再扫描一次， 加入所有 x_i\le a 的直线并维护最大高度。

只需要在询问出现过的横坐标 b 上求值。 将这些坐标排序去重后，使用离散李超树维护最小值或最大值。 比较直线 i,j 在 z 处的高度时，不进行除法。 因为 x_i,x_j>0，有：

所有乘法使用 128 位整数，避免溢出与浮点误差。

还需单独处理退化线段。

若 y_i=0，给定线段是 x 轴上的区间 [0,x_i]。 记所有这类线段的最大右端点为 h_x。 当询问终点满足 c>0 时，询问只在起点接触 x 轴， 相交条件为 a\le h_x。 当 c=0 时，询问也位于 x 轴上， 相交条件为 \min(a,b)\le h_x。

若 x_i=0，给定线段是 y 轴上的区间 [0,y_i]。 记最大上端点为 v_y。 询问与它相交，当且仅当：

• 或 b=0 且 c\le v_y，此时询问终点落在线段上。

原点线段同时属于两类退化判断，不会影响布尔答案。

正确性证明

对于非退化给定线段，询问线段完全位于第一象限闭区域。 两条线段相交等价于询问两个端点分处给定直线两侧或在线上。 起点相对直线的位置只由 a 与 x_i 的大小决定， 所以所有可能相交分别被两式