AdditionalFile3404.zip

#3404. 「2020-2021 集训队作业」Defend City

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

题目描述

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)$ 都能被保护。你能找到最优策略吗？

输入格式

输入的第一行给出了测试点组数 $T$，接下来是 $T$ 组测试点。

对于每组测试点，第一行包含一个整数 $n$，其中 $n$ 是防御塔的数量。

接下来的 $n$ 行，每行包含三个整数 $x_i,y_i$ 和 $d_i$，表示防御塔 $i$ 的位置和方向。

输出格式

对于每组测试点，输出一行包含 "\texttt{Case #x: y}"，其中 $\texttt{x}$ 是测试点编号（从 $1$ 开始），以及 $\texttt{y}$ 是最少数量的防御塔。如果不可能保护整座城池，输出 "$\texttt{Impossible}$"（不包括引号）。

样例

输入

2
3
1 1 1
2 2 2
3 3 3
4
1 1 1
2 2 3
2 1 2
1 2 4

输出

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$。

由于本题输入量较大，请使用较快的读入方式。