P14434 [JOISC 2013] 建设项目 / Construction Project

IOI 国决定对交通网络进行全面改造。IOI 国可表示为 $xy$ 坐标平面，其上有 $N$ 个城镇。第 $i$ 个（$1 \leq i \leq N$）城镇表示为点 $(X_i, Y_i)$。交通网改造按以下步骤进行： - 在 $N$ 个城镇中选择若干城镇建设国际机场。至少需建设一个国际机场。每建设一个国际机场需花费固定成本。 - 铺设若干条连接城镇的道路。道路是连接代表城镇的点、且与 $x$ 轴或 $y$ 轴平行的线段。每铺设一条道路，其成本等于该道路的长度。 此时，必须满足以下条件： - IOI 国存在 $M$ 个因地质条件恶劣等原因无法铺设道路的区域。每个区域用一个矩形表示，第 $j$ 个（$1 \leq j \leq M$）矩形的左下角点为 $(P_j, Q_j)$，右上角点为 $(R_j, S_j)$（即 $P_j < R_j$ 且 $Q_j < S_j$）。任何道路不得与 $M$ 个区域中的任何一个有重叠部分。区域包含其边界，因此道路也不得与表示区域的矩形边界有重叠。 - 从 $N$ 个城镇中的任意一个出发，必须能通过反复沿道路前往其他城镇，最终到达建有国际机场的城镇。 该项目的承包方候选为 $C$ 家建筑公司。第 $k$ 家（$1 \leq k \leq C$）建筑公司建设一个国际机场的成本为 $B_k$，且最多能建设 $H_k$ 个国际机场（道路建设成本与建筑公司无关，且道路的数量和长度无限制）。对于每家建筑公司，希望求出该公司在满足上述条件下进行交通网改造所需总成本的最小值。 由于可建设的国际机场数量有限，可能存在某些建筑公司无法以任何方式满足条件。此时不应报告总成本，而应报告无法满足条件。 ### 任务 给定表示 IOI 国城镇数量的整数 $N$ 及各城镇坐标、表示无法铺设道路区域数量的整数 $M$ 及各区域坐标、表示承包方候选建筑公司数量的整数 $C$ 及各公司信息，编写程序对每家建筑公司，计算在满足题目所述条件下进行交通网改造所需总成本的最小值。

从标准输入读取以下输入数据： - 第 $1$ 行包含三个以空格分隔的整数 $N, M, C$，分别表示 IOI 国中的城镇数量、无法铺设道路的区域数量、项目承包方候选建筑公司数量。 - 后续 $N$ 行中，第 $i$ 行（$1 \leq i \leq N$）包含两个以空格分隔的整数 $X_i, Y_i$，表示第 $i$ 个城镇的坐标为 $(X_i, Y_i)$。 - 后续 $M$ 行中，第 $j$ 行（$1 \leq j \leq M$）包含四个以空格分隔的整数 $P_j, Q_j, R_j, S_j$，表示第 $j$ 个无法铺设道路的区域所对应矩形的左下角点坐标为 $(P_j, Q_j)$，右上角点坐标为 $(R_j, S_j)$。 - 后续 $C$ 行中，第 $k$ 行（$1 \leq k \leq C$）包含两个以空格分隔的整数 $B_k, H_k$，表示第 $k$ 个承包方候选建筑公司建设一个国际机场的成本为 $B_k$，且最多能建设 $H_k$ 个国际机场。

向标准输出输出 $C$ 行。第 $k$ 行（$1 \leq k \leq C$）输出一个整数，表示第 $k$ 个承包方候选建筑公司实施该项目所需总成本的最小值。若第 $k$ 个承包方候选建筑公司无法以任何方式满足条件，则输出整数 $-1$。

### 样例 1 解释 该输入示例的图示如下。粗线矩形表示无法铺设道路的区域。 :::align{center}  ::: 虽然可以铺设连接城镇 $2$ 与城镇 $4$、以及城镇 $3$ 与城镇 $4$ 的道路，但由于会与无法铺设道路的区域相交，因此无法在城镇 $1$ 与城镇 $2$ 之间铺设道路。同理，城镇 $1$ 与城镇 $3$ 之间也无法铺设道路（请注意道路不得与矩形边界有任何重叠部分）。 第一家建筑公司最多可建设 $4$ 个国际机场，每个成本为 $7$。此时，最优方案是不铺设任何道路而在所有城镇建设国际机场，总成本为 $7 \times 4 = 28$。 第二家建筑公司最多可建设 $3$ 个国际机场，每个成本为 $10$。此时，最优方案之一是铺设连接城镇 $2$ 与城镇 $4$、以及城镇 $3$ 与城镇 $4$ 的长度为 $9$ 的道路，并在城镇 $1$ 与城镇 $2$ 建设国际机场，总成本为 $10 \times 2 + 9 + 9 = 38$。 第三家建筑公司最多可建设 $1$ 个国际机场，每个成本为 $1$。但由于城镇 $1$ 无法与任何其他城镇之间铺设道路，为满足题目条件至少需要建设 $2$ 个国际机场，因此该公司无法完成项目，应输出 $-1$。 ### 限制 所有输入数据满足以下条件： - $1 \leq N \leq 200\,000$ - $1 \leq M \leq 200\,000$ - $1 \leq C \leq 500\,000$ - $0 \leq X_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$) - $0 \leq Y_i \leq 1\,000\,000\,000$ ($1 \leq i \leq N$) - 同一坐标不存在两个及以上城镇 - $0 \leq P_j < R_j \leq 1\,000\,000\,000$ ($1 \leq j \leq M$) - $0 \leq Q_j < S_j \leq 1\,000\,000\,000$ ($1 \leq j \leq M$) - 任何区域均不包含城镇于其矩形内部或边界上 - $1 \leq B_k \leq 1\,000\,000\,000$ ($1 \leq k \leq C$) - $1 \leq H_k \leq N$ ($1 \leq k \leq C$) ### 子任务 #### 子任务 1 [10 分] 满足以下条件： - $M \leq 100$ - $C \leq 100$ #### 子任务 2 [30 分] 满足以下条件： - $C \leq 100$ #### 子任务 3 [30 分] 满足以下条件： - $M \leq 100$ #### 子任务 4 [30 分] 无额外限制。 翻译由 DeepSeek V3 完成