← 返回题目列表

Codeforces · 1027/C

C. 最小值矩形

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

你有 $$$n$$$ 给定长度的木棍。

你的任务是选择其中的四个,使它们能够形成一个矩形。任何木棍都不能被切成碎片,矩形的每条边都必须由一根木棍组成。没有一根棍子不能被多次选择。保证总是可以选择这样的棍子。

设 $$$S$$$ 为矩形的面积,$$$P$$$ 为矩形的周长。

所选矩形应具有尽可能小的值 $$$\frac{P^2}{S}$$$。该值未经任何舍入而取。

如果有多个答案,请打印其中任何一个。

每个测试用例都包含多个棍子列表,对于每个棍子,您都需要单独解决问题。

输入

第一行包含一个整数 $$$T$$$ ($$$T \ge 1$$$) — 测试用例中棍子列表的数量。

然后是 $$$2T$$$ 行 — 其中 $$$(2i - 1)$$$ 行和 $$$2i$$$ 描述第 $$$i$$$ 列表。该对的第一行包含一个整数 $$$n$$$ ($$$4 \le n \le 10^6$$$) — 第 $$$i$$$ 列表中的棒数。该对的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_j \le 10^4$$$) — 第 $$$i$$$ 列表中棒的长度。

保证对于每个列表,都有一种方法可以选择四根棍子,使它们形成一个矩形。

每个测试用例中所有 $$$T$$$ 列表中的棒总数不超过 $$$10^6$$$。

输出

打印 $$$T$$$ 行。第 $$$i$$$ 行应包含第 $$$i$$$ 输入列表的答案。这是您从第 $$$i$$$ 列表中选择的四根棍子的长度,以便它们形成一个矩形,并且该矩形的值 $$$\frac{P^2}{S}$$$ 尽可能小。您可以按任意顺序打印这四个长度。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
4
7 2 2 7
8
2 8 1 4 8 2 1 5
5
5 5 5 5 5

输出 #1

2 7 7 2
2 2 1 1
5 5 5 5

注意

第一个列表中只有一种选择四根棍子的方法,它们形成一个边长为 $$$2$$$ 和 $$$7$$$ 的矩形,其面积为 $$$2 \cdot 7 = 14$$$,周长为 $$$2(2 + 7) = 18$$$。 $$$\frac{18^2}{14}\约23.143$$$。

第二个列表包含四根棍子的子集,这些棍子可以形成边长为 $$$(1, 2)$$$、$$$(2, 8)$$$ 和 $$$(1, 8)$$$ 的矩形。它们的值分别为 $$$\frac{6^2}{2} = 18$$$、$$$\frac{20^2}{16} = 25$$$ 和 $$$\frac{18^2}{8} = 40.5$$$。其中最小的一个是矩形 $$$(1, 2)$$$。

你可以从第三个列表中选择任意四根给定的 $$$5$$$ 棒,它们将形成一个边长为 $$$5$$$ 的正方形,这仍然是一个边长为 $$$(5, 5)$$$ 的矩形。