P14695 [ICPC 2024 Tehran R] Electromagnetic Attacks

本题的官方时限未知。

在 Barareh，一个点对点（P2P）无线网络被用于连接基站，以提供私有数据服务。在 P2P 无线网络中，每个基站使用一些定向天线来与其他基站连接。如果将基站建模为点，通信链路建模为线段，那么 Barareh 的 P2P 网络出人意料地具有一些几何特性。具体来说，该网络是一个平面图，其外部边界是一个凸多边形，且所有内部面都是三角形。 在近期的世界冲突中，一个重要问题困扰着 Barareh 的信息与通信技术（ICT）部长 Khorzukhan。他想知道该网络对电磁攻击的韧性如何。在一次电磁攻击中，噪声会在某个区域（即攻击区域）产生，从而破坏所有穿过该区域的通信。剩余网络由所有严格位于攻击区域外的基站和通信链路组成。具体来说，Khorzukhan 想知道剩余网络是否保持连通。为此，他已指示其部门分别模拟多次电磁攻击，测试网络对干扰的容忍度，并报告每次模拟后剩余网络是否保持连通。

输入的第一行包含 $n$、$m$ 和 $k$ ($3 \leq n \leq 10^5$， $3 \leq m \leq 3 \cdot 10^5$， $1 \leq k \leq 10^5$)，分别表示基站的数量、通信链路的数量和攻击模拟的次数。 接下来的 $n$ 行中，第 $i$ 行包含第 $i$ 个基站的 $x$ 和 $y$ 坐标，两者均为非负整数 ($0 \leq x, y \leq 10^9$)。保证并非所有基站共线。 接下来的 $m$ 行中的每一行代表一条通信链路。每行包含两个整数 $i$ 和 $j$ ($1 \leq i, j \leq n$)，表示一条连接第 $i$ 个和第 $j$ 个基站的直线段。这 $m$ 条通信链路构成一个平面图。外部边界是一个凸多边形，且内部面均为三角形。 最后，攻击区域信息在接下来的 $k$ 行中给出。每个攻击区域是一个非空矩形，由其左下角和右上角的坐标 $x_1, y_1, x_2, y_2$ 表示 ($0 \leq x_1 < x_2 \leq 10^9$， $0 \leq y_1 < y_2 \leq 10^9$)。所有矩形的边都平行于坐标轴。请注意，如果一个基站或一条链路的部分（即使是一个点）位于攻击区域内（包括边界），则在攻击期间该基站或链路不可用。

输出 $k$ 行。对于每次攻击模拟，如果攻击导致的剩余网络是连通的，则输出 **Yes**；否则输出 **No**。如果所有基站都位于攻击区域内，剩余网络变为空，但仍被视为连通。

在第一次攻击模拟中，第一个和第三个基站在攻击区域外；然而，它们彼此不连通。 :::align{center}  ::: 翻译由 DeepSeek V3 完成