A5953. 「2020-2021 集训队作业」Defend City
编程题
NOI/NOI+/CTSC
知识点
题目描述
Alex 是一位电竞选手。
这些天，Alex 正在玩一款战争策略游戏。他的城池可以被看做笛卡尔平面上的一个矩形，它的左下角为 $(0,0)$，右上角为 $(n+1,n+1)$。
Alex 建造了 $n$ 座防御塔来保卫城池。防御塔 $i$ 位于 $(x_i,y_i)$，方向为 $d_i$。方向不同的防御塔能够保护不同的区域，具体来说：
- 若 $d_i = 1$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \ge x_i, b \ge y_i\}$；
- 若 $d_i = 2$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \le x_i, b \ge y_i\}$；
- 若 $d_i = 3$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \le x_i, b \le y_i\}$；
- 若 $d_i = 4$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \ge x_i, b \le y_i\}$。
如果 Alex 启用了 $e$ 座防御塔，他每小时将会消耗 $e$ 的单位能量。他想要启用尽量少数量的防御塔，使得城池中的任何点 $(x,y)(x,y \in \mathbb{R}, 0 \le x,y \le n+1)$ 都能被保护。你能找到最优策略吗？
这些天，Alex 正在玩一款战争策略游戏。他的城池可以被看做笛卡尔平面上的一个矩形，它的左下角为 $(0,0)$，右上角为 $(n+1,n+1)$。
Alex 建造了 $n$ 座防御塔来保卫城池。防御塔 $i$ 位于 $(x_i,y_i)$，方向为 $d_i$。方向不同的防御塔能够保护不同的区域，具体来说：
- 若 $d_i = 1$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \ge x_i, b \ge y_i\}$；
- 若 $d_i = 2$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \le x_i, b \ge y_i\}$；
- 若 $d_i = 3$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \le x_i, b \le y_i\}$；
- 若 $d_i = 4$，防御塔 $i$ 能保护区域 $\{(a,b) \mid a \ge x_i, b \le y_i\}$。
如果 Alex 启用了 $e$ 座防御塔，他每小时将会消耗 $e$ 的单位能量。他想要启用尽量少数量的防御塔，使得城池中的任何点 $(x,y)(x,y \in \mathbb{R}, 0 \le x,y \le n+1)$ 都能被保护。你能找到最优策略吗？
输入格式
输入的第一行给出了测试点组数 $T$，接下来是 $T$ 组测试点。
对于每组测试点，第一行包含一个整数 $n$，其中 $n$ 是防御塔的数量。
接下来的 $n$ 行，每行包含三个整数 $x_i,y_i$ 和 $d_i$，表示防御塔 $i$ 的位置和方向。
对于每组测试点，第一行包含一个整数 $n$，其中 $n$ 是防御塔的数量。
接下来的 $n$ 行，每行包含三个整数 $x_i,y_i$ 和 $d_i$，表示防御塔 $i$ 的位置和方向。
输出格式
对于每组测试点，输出一行包含 "$\texttt{Case #x: y}$"，其中 $\texttt{x}$ 是测试点编号（从 $1$ 开始），以及 $\texttt{y}$ 是最少数量的防御塔。如果不可能保护整座城池，输出 "$\texttt{Impossible}$"（不包括引号）。
输入输出样例
输入 #1
2 3 1 1 1 2 2 2 3 3 3 4 1 1 1 2 2 3 2 1 2 1 2 4
输出 #1
Case #1: Impossible Case #2: 4
说明/提示
对于 $10\%$ 的测试数据，满足 $n \le 20,\ \sum n \le 100$。
对于 $30\%$ 的测试数据，满足 $n \le 100,\ \sum n \le 500$。
对于 $40\%$ 的测试数据，满足 $n \le 1000,\ \sum n \le 5000$。
对于 $70\%$ 的测试数据，满足 $n \le 10^5,\ \sum n \le 5 \times 10^5$。
对于全部测试数据，满足 $1 \le T \le 10^4,\ 1 \le n \le 10^6,\ \sum n \le 5 \times 10^6,\ 1 \le x_i,y_i \le n,\ 1 \le d_i \le 4$。
**由于本题输入量较大，请使用较快的读入方式。**
对于 $30\%$ 的测试数据，满足 $n \le 100,\ \sum n \le 500$。
对于 $40\%$ 的测试数据，满足 $n \le 1000,\ \sum n \le 5000$。
对于 $70\%$ 的测试数据，满足 $n \le 10^5,\ \sum n \le 5 \times 10^5$。
对于全部测试数据，满足 $1 \le T \le 10^4,\ 1 \le n \le 10^6,\ \sum n \le 5 \times 10^6,\ 1 \le x_i,y_i \le n,\ 1 \le d_i \le 4$。
**由于本题输入量较大，请使用较快的读入方式。**