题解：树可见区域与安全路径的几何判定

---

问题分析

本题要求判断小G能否从起点安全走到各个营地，条件是在整条路径上都能看到所有树。关键约束：

• 小G能看到一棵树当且仅当连接线段上没有其他树
• 起点能看到所有树
• 每个营地也能看到所有树
• 树木视为点，无三点共线

问题转化为：判断是否存在一条从起点到营地的路径，使得路径上任意点对每棵树的视线都不被其他树遮挡。

---

核心观察

1. 视线遮挡条件

对于一棵树 $T$，另一棵树 $T'$ 会遮挡 $T$ 当且仅当观察点 $P$ 位于线段 $TT'$ 的延长线区域内。

具体来说，设 $T$ 和 $T'$ 的坐标，则：

• $T'$ 遮挡 $T$ 的区域是：以 $T$ 为原点，$T'$ 的对称点 $T'' = 2T - T'$ 为方向的射线区域
• 这是因为当观察点 $P$ 在 $T$ 和 $T''$ 连线上时，$T'$ 恰好在 $P$ 和 $T$ 之间

2. 安全区域

对于每棵树 $T_i$，所有会遮挡它的树 $T_j$ 定义了若干个"危险方向"。安全区域就是避开所有这些危险方向的区域。

更精确地：对于树 $T_i$，所有其他树 $T_j$ 定义了一个危险方向 $T_i \to (2T_i - T_j)$。安全观察点必须不在这些方向的直线上，且在某些限制区域内。

3. 关键定理

经过分析可得：小G能安全走到营地 $C$ 当且仅当对于每棵树 $T_i$，营地 $C$ 相对于 $T_i$ 的位置与起点 $O$ 相对于 $T_i$ 的位置在同一个"可见半平面"内。

这个条件等价于：对于每棵树 $T_i$，营地 $C$ 在由 $T_i$ 和所有其他树 $T_j$ 定义的某个角度区间内。

---

算法框架

第一步：计算每棵树的可见区间

对于每棵树 $T_i$：

1. 计算所有对称点 $T_{ij} = 2T_i - T_j$（$j \neq i$）
2. 将这些对称点按极角排序
3. 确定包含起点 $O$ 的极角区间 $[L_i, R_i]$
   • 实际上，代码中计算的是 l[i] 和 r[i]，即最小和最大的对称点（按特定排序规则）

第二步：判断营地是否安全

对于每个营地 $Q_k$：

• 检查是否对于所有树 $T_i$，$Q_k$ 都在 $T_i$ 的可见区间内
• 即：$Q_k$ 相对于 $T_i$ 的极角在 $[L_i, R_i]$ 内

第三步：排序规则

代码中的排序规则 operator< 基于：

1. 相对于当前树 $T_i$（st）和起点 $O$ 的位置关系
2. 首先按是否在起点所在的半平面分类
3. 然后按极角排序

这确保了 l[i] 和 r[i] 正确表示了包含起点的可见区间边界。

---

关键实现细节

1. 向量运算

• 叉积 *：判断方向关系
• 点积 dot：判断共线时的相对位置
• area 函数：判断点相对于起点 $O$ 和当前树 $T_i$ 的位置关系

2. 极角排序

排序比较器考虑了：

• 是否在由起点 $O$ 定义的半平面内
• 极角大小（通过叉积判断）

3. 区间检查

!(r[j] < q[i] || q[i] < l[j]) 等价于检查点 $Q_k$ 是否在区间 $[l[j], r[j]]$ 内（按定义的序）。

---

复杂度分析

• 时间复杂度：$O(N^2 + N \cdot C)$
  • 计算每棵树的对称点：$O(N^2)$
  • 对每个营地检查所有树：$O(N \cdot C)$
  • 对于 $N \le 2000, C \le 10000$，最坏约 $2\times 10^7$ 次操作，可接受
• 空间复杂度：$O(N)$

---

正确性证明

核心引理

对于固定树 $T$，观察点 $P$ 能看到 $T$ 当且仅当对于所有其他树 $T'$，$P$ 不在线段 $TT'$ 的"延长遮挡区域"内。

区间表示

将所有对称点 $2T - T'$ 按极角排序后，包含起点 $O$ 的连续区间就是安全观察区域。这是因为：

• 如果 $P$ 在这个区间外，则存在某个 $T'$ 使得 $P$ 在 $T$ 和 $2T - T'$ 的连线上
• 这意味着 $T'$ 在 $P$ 和 $T$ 之间，遮挡了视线

路径存在性

由于安全区域是凸的（实际上是星形区域），如果起点 $O$ 和营地 $C$ 都在同一安全区域内，则存在直线路径连接它们，且路径上所有点都保持可见性。

---

总结

本题是一道计算几何与可见性分析的难题，主要考察：

1. 几何转化能力：将视线遮挡问题转化为极角区间问题
2. 对称技巧：使用 $2T_i - T_j$ 巧妙表示遮挡方向
3. 极角排序：高效处理角度关系
4. 区间判定：判断点是否在角度区间内

算法的巧妙之处在于：

• 通过对称变换将遮挡条件线性化
• 利用极角排序确定安全观察区域
• 将复杂的可见性保持问题简化为区间包含检查

这种"对称点+极角区间"的方法在视线遮挡问题中具有通用性，是处理此类"看到所有点"条件的经典技巧。