题目详情题解（0）讨论（0）提交记录（0）

CF2038C.DIY

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 nn 的整数数列 aa，下标从 11 到 nn。你需要从 aa 中选择 88 个下标互不相同的数 x1,y1,x2,y2,x3,y3,x4,y4x1,y1,x2,y2,x3,y3,x4,y4，并使 (x1,y1),(x2,y2),(x3,y3),(x4,y4)(x_1,y_1),(x_2,y_2),(x_3,y_3),(x_4,y_4) 成为一个长方形的四个点的坐标，且边与坐标轴平行或垂直。请构造一种方案使得此长方形面积最大，或报告无解。

输入格式

本题多测。

第一行一个整数 t(1≤t≤25000)t(1\le t\le 25000)，代表测试样例组数。

对于每组测试样例：

第一行一个整数 n(8≤n≤2×105)n(8\le n\le 2\times 10^5)。

第二行 nn 个整数 a1,a2,…,an(−109≤ai≤109)a_1,a_2,\dots,a_n(-10^9\le a_i\le 10^9)。

保证 ∑n≤2×105\sum n\le 2\times 10^5。

输出格式

对于每组测试样例：

若无解，输出一行 NO（不区分大小写）。

否则，第一行输出 YES（不区分大小写），第二行输出 x1,y1,x2,y2,x3,y3,x4,y4x1,y1,x2,y2,x3,y3,x4,y4——长方形的四个点的坐标。你可以按任意顺序打印坐标对。

Translated by @ARIS2_0

输入输出样例

  • 输入#1

    3
16
-5 1 1 2 2 3 3 4 4 5 5 6 6 7 7 10
8
0 0 -1 2 2 1 1 3
8
0 0 0 0 0 5 0 5

    输出#1

    YES
1 2 1 7 6 2 6 7
NO
YES
0 0 0 5 0 0 0 5

输入解题思路，AI测评打分。不知道怎么写?

首页