CF2046C Adventurers

曾经，四位罗马商人在一座罗马宅邸中相聚，商讨他们的贸易计划。他们遇到了如下问题：他们都经营同一种商品，如果在同一座城市进行贸易，必然会遭受损失。于是他们决定将各自的贸易城市进行划分。 在本题中，罗马的地图可以表示为一个平面，其中标记了一些点——即罗马帝国的城市。 商人们决定选择一个划分点 $ (x_0, y_0) $。那么，对于坐标为 $ (x_i, y_i) $ 的城市： - 如果 $ x_0 \le x_i $ 且 $ y_0 \le y_i $，则第一位商人在该城市售卖商品； - 如果 $ x_0 > x_i $ 且 $ y_0 \le y_i $，则第二位商人在该城市售卖商品； - 如果 $ x_0 \le x_i $ 且 $ y_0 > y_i $，则第三位商人在该城市售卖商品； - 如果 $ x_0 > x_i $ 且 $ y_0 > y_i $，则第四位商人在该城市售卖商品。 商人们希望选择 $ (x_0, y_0) $，使得每个人分到的城市数最少值最大（即尽可能公平）。请你帮他们找到这样的一个点。

每个测试点包含多组测试数据。第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $），表示测试数据组数。 每组测试数据的第一行包含一个整数 $ n $（$ 4 \le n \le 10^5 $），表示地图上的城市数量。 接下来的 $ n $ 行，每行包含两个整数 $ x_i, y_i $（$ -10^9 \le x_i, y_i \le 10^9 $），表示每座城市的坐标。 注意，某些点可能重合。这是因为有些城市距离太近，在给定的比例尺下无法区分。 保证所有测试数据中 $ n $ 的总和不超过 $ 10^5 $。

对于每组测试数据，第一行输出一个整数 $ k $（$ 0 \le k \le \frac{n}{4} $），表示每位商人最少能分到的最大城市数。 第二行输出两个整数 $ x_0 $ 和 $ y_0 $（$ |x_0|, |y_0| \le 10^9 $），表示划分点的坐标。如果有多个满足条件的点，输出任意一个均可。

由 ChatGPT 4.1 翻译