← 返回题目列表

Codeforces · 2046/C

C. 冒险家

中文机器翻译题面 查看原题

有一次,四位罗马商人在一座罗马宅邸里开会讨论他们的贸易计划。他们面临着这样的问题:他们交易的是同一种商品,如果在同一个城市交易,必然会产生损失。他们决定划分他们之间进行贸易的城市。

在这个问题中,罗马地图可以表示为一个平面,上面标有某些点——罗马帝国的城市。

商家决定选择某个分割点$$$(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$$$) – 分割点的坐标。如果有多个合适的点,则打印其中任意一个。

示例

输入 #1

4
4
1 1
1 2
2 1
2 2
4
0 0
0 0
0 0
0 0
8
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1
-2 1
-1 2
7
1 1
1 2
1 3
1 4
2 1
3 1
4 1

输出 #1

1
2 2
0
0 0
2
1 0
0
0 0