#5115. 「JOISC 2013 Day2」建设项目

题目描述

题目译自 JOISC 2013 Day2 T1 「建設事業」

在 IOI 国，一项大规模交通网络整备计划正在展开。IOI 国可以看作一个 $xy$ 坐标平面，上面分布着 $N$ 个城镇。第 $i$ $(1 \leq i \leq N)$ 个城镇位于坐标 $(X_{i}, Y_{i})$。交通网络的整备将按照以下步骤进行：

1. 在 $N$ 个城镇中选择若干个建设国际机场，至少需要建设 $1$ 个。每次建设国际机场都会产生固定的成本。
2. 在城镇之间铺设若干道路。道路是连接城镇的点之间、平行于 $x$ 轴或 $y$ 轴的线段，每铺设一条道路的成本等于其长度。

在整备过程中，必须满足以下条件：

1. 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$ 个区域有任何交集，包括区域的边界在内，道路也不得与长方形区域的边界有公共部分。
2. 从任意一个城镇出发，通过道路辗转前往其他城镇，最终必须能够到达某个设有国际机场的城镇。

作为该项目的潜在承包商，$C$ 家公司被列入候选名单。第 $k$ $(1 \leq k \leq C)$ 家公司建设一个国际机场的成本为 $B_{k}$，并且最多能建设 $H_{k}$ 个国际机场（铺设道路的成本不因公司而异，且道路数量和长度没有限制）。你需要为每家公司计算，在满足上述条件的前提下，进行交通网络整备所需的最小总成本。

由于有些公司能建设的国际机场数量有限，可能无法满足条件。对于无法满足条件的公司，请报告无法完成任务，而非给出成本值。

给定 IOI 国城镇数量 $N$ 及其坐标、不可铺设道路区域数量 $M$ 及其坐标、候选建设公司数量 $C$ 及各公司信息，你需要编写一个程序，为每家建设公司计算在满足题目所述条件的情况下，进行交通网络整备所需的最小总成本。

---

输入格式

从标准输入中读取以下数据：

• 第一行包含三个整数 $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$。

---

样例

输入

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

输出

28
38
-1

此输入样例图示如下，粗线矩形表示不可铺设道路的区域。

可以铺设连接城镇 $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 200000$
• $1 \leq M \leq 200000$
• $1 \leq C \leq 500000$
• $0 \leq X_{i} \leq 1000000000$ $(1 \leq i \leq N)$
• $0 \leq Y_{i} \leq 1000000000$ $(1 \leq i \leq N)$
• 同一坐标不会有多个城镇。
• $0 \leq P_{j} < R_{j} \leq 1000000000$ $(1 \leq j \leq M)$
• $0 \leq Q_{j} < S_{j} \leq 1000000000$ $(1 \leq j \leq M)$
• 任何区域都不会将城镇包含在其内部或边界上。
• $1 \leq B_{k} \leq 1000000000$ $(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		$M \leq 100$
4		无附加限制

---