题目描述

随着线上课程的全面展开，Grace 需要适时休息并时刻保持水分。她决定在房间中最方便的位置放置一个水瓶。这意味着这个水瓶的位置应该靠近她经常活动的所有地方，比如书桌、床和咖啡桌等。

房间可以用一个坐标平面来表示。Grace 从点 $A$ 到点 $B$ 所需的步数等于两点之间的曼哈顿距离。也就是说，她只能平行于坐标轴行走，每一步可以向四个方向之一移动 $1$ 个单位。

你能帮她找到一个放置水瓶的位置，使得从水瓶到所有她喜欢的家具的步数之和最小吗？

注意：

• 所有家具（如书桌、床或咖啡桌）都可以表示为平面上面积非零且边平行于坐标轴的矩形。
• 家具之间可能重叠，因为她喜欢在床上用桌板工作。
• 假设 Grace 行走时可以径直穿过家具，无需绕行。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含一个整数 $K$，表示 Grace 房间中物品的数量。

接下来 $K$ 行，每行描述一个物品。第 $i$ 行包含四个整数 $x_{i,1}$、$y_{i,1}$、$x_{i,2}$、$y_{i,2}$，其中 $(x_{i,1}, y_{i,1})$ 表示第 $i$ 个矩形物体的左下角坐标，$(x_{i,2}, y_{i,2})$ 表示其右上角坐标。

输出格式

对于每个测试用例，输出一行，格式为 Case #i: x y，其中 $i$ 是测试用例编号（从 $1$ 开始），$x$ 和 $y$ 是放置水瓶的坐标，使得从这些坐标到所有家具的步数之和最小。

注意，水瓶可以放在地板上或任何家具的上面，但必须放置在整数坐标上。

如果存在多个解，输出 $x$ 坐标最小的解；如果多个解的 $x$ 坐标相同，输出 $y$ 坐标最小的解。

2
3
0 0 1 1
2 3 4 6
0 3 5 9
1
0 0 1 1

Case #1: 1 3
Case #2: 0 0

提示

:::align{center} :::

在样例 #1 中，Grace 可以将水瓶放在坐标 $(1, 3)$ 处。它到第 $1$ 个物体的距离为 $2$ 步，到第 $2$ 个物体为 $1$ 步，到第 $3$ 个物体为 $0$ 步，总步数为 $3$，这是从某点出发所能达到的最小可能步数之和。

在样例 #2 中，水瓶可以放在物体上的任何位置，但坐标 $(0, 0)$ 对应最小的 $x$ 和 $y$ 坐标。

限制条件

$1 \le T \le 100$。

对于所有 $i$，$x_{i,1} < x_{i,2}$。

对于所有 $i$，$y_{i,1} < y_{i,2}$。

测试集 1

$1 \le K \le 20$。

对于所有 $i$，$-100 \le x_{i,1}, x_{i,2}, y_{i,1}, y_{i,2} \le 100$。

测试集 2

$1 \le K \le 10^5$。

对于所有 $i$，$-10^9 \le x_{i,1}, x_{i,2}, y_{i,1}, y_{i,2} \le 10^9$。

翻译由 DeepSeek V4 Pro 完成