P13334 [GCJ 2012 Finals] Xeno-archaeology

很久以前，一个外星文明建造了一座巨大的纪念碑。纪念碑的地板图案如下： ``` ############### #.............# #.###########.# #.#.........#.# #.#.#######.#.# #.#.#.....#.#.# #.#.#.###.#.#.# #.#.#.#.#.#.#.# #.#.#.###.#.#.# #.#.#.....#.#.# #.#.#######.#.# #.#.........#.# #.###########.# #.............# ############### ``` 每个 `#` 代表一块红色瓷砖，每个 `.` 代表一块蓝色瓷砖。这个图案曾经向四面八方无限延展（在本题中，你可以假设它是无限的）。而今天，只剩下少量瓷砖还留存，其他的都被甲烷雨和尘暴损坏了。现给出所有还剩下的瓷砖的位置和颜色，你能否找出这个图案的中心位置？

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据第一行为整数 $N$，表示剩余瓷砖的数量。接下来的 $N$ 行，每行包含 $X_i$、$Y_i$ 以及瓷砖颜色（`#` 或 `.`）。

对于每个测试用例，输出一行 "Case #$c$: $X$ $Y$"，其中 $c$ 为测试用例编号（从 1 开始），($X$, $Y$) 为图案中心的位置。如果有多个可能的答案，输出与 $(0, 0)$ 曼哈顿距离（$|X| + |Y|$）最小的那个。如果仍有多解，输出 $X$ 最大的那个；如果仍有多解，输出 $Y$ 最大的那个。如果无解，输出 "Case #$c$: Too damaged"。

**限制条件** - $1 \leq T \leq 50$。 - 每组测试数据中的坐标不会重复。 **测试集 1（12 分，结果可见）** - $1 \leq N \leq 100$。 - $-100 \leq X_i \leq 100$。 - $-100 \leq Y_i \leq 100$。 **测试集 2（33 分，结果隐藏）** - $1 \leq N \leq 1000$。 - $-10^{15} \leq X_i \leq 10^{15}$。 - $-10^{15} \leq Y_i \leq 10^{15}$。 翻译由 ChatGPT-4.1 完成。