题目理解

给定一个包含 $n$ 个整数的列表 $a_1, a_2, \dots, a_n$。
我们需要从中选出 $8$ 个元素作为四个点的坐标，这四个点构成一个边与坐标轴平行的矩形。
矩形的四个顶点为：

$$(x_1, y_1),\ (x_1, y_2),\ (x_2, y_1),\ (x_2, y_2)$$

其中 $x_1 \ne x_2$，$y_1 \ne y_2$。

目标是使矩形面积 $S = |x_1 - x_2| \times |y_1 - y_2|$ 最大。
若无法构造，输出 $NO$。

---

关键观察

$1$. 每个坐标值（$x_1, x_2, y_1, y_2$）在矩形中出现的次数：

• 若四个值互不相同，每个值出现恰好 $2$ 次（因为每个 $x$ 对应两个 $y$，每个 $y$ 对应两个 $x$）。
• 若 $x_1 = y_1$，则该值出现在三个点中：$(x_1,y_1)$、$(x_1,y_2)$、$(x_2,y_1)$，因此至少需要出现 $3$ 次。
• 若 $x_1 = y_1$ 且 $x_2 = y_2$，则每个值出现 $2$ 次，但此时矩形退化为线段（面积 $0$）。
• 若 $x_1 = y_2$ 且 $x_2 = y_1$，同理。

$2$. 为了最大化面积，我们应让 $x_1$ 和 $x_2$ 尽量远离，$y_1$ 和 $y_2$ 尽量远离。
因此最优的 $x_1, x_2$ 应该是候选值中最小和最大的，最优的 $y_1, y_2$ 应该是候选值中第二小和第二大（若互不相同且出现次数足够）。

$3$. 候选值：在原列表中出现次数 $\ge 2$ 的数。因为每个值在矩形中至少出现 $2$ 次（除非特殊重复情况，但重复会减小面积）。

---

算法步骤

$1$. 统计每个值的出现次数 $cnt$。 $2$. 收集所有出现次数 $\ge 2$ 的值到 $cand$ 数组。 $3$. 若 $cand.size() < 2$，则无法构造矩形（至少需要两个不同的 $x$ 和两个不同的 $y$，但可能通过重复值实现，不过面积 $0$，且需要出现次数足够，这里简化处理，直接判 $NO$）。 $4$. 对 $cand$ 排序。 $5$. 设 $x_1 = \min(cand)$，$x_2 = \max(cand)$（这样 $x$ 的差最大）。 $6$. 尝试找出最优的 $y_1, y_2$（$y_1 \ne y_2$，且出现次数足够）：

• 优先尝试 $$(cand[1], cand[m-2])$$（若 $m \ge 4$），因为这是次小和次大，差尽可能大且与 $x$ 不同。
• 若 $x_1, x_2$ 与 (cand[1], cand[m-2]) 有冲突，则尝试其他组合：
  • 若 $x_1, x_2$ 出现次数 $\ge 3$，则 $y$ 也可以取 $x_1, x_2$（此时 $y$ 与 $x$ 重合，需要检查次数）。
  • 尝试 $$(cand[0], cand[m-2])$$ 和 $$(cand[1], cand[m-1])$$，确保不违反出现次数。
• 若 $m = 2$，则只有两个候选值，此时只能取 $y_1 = x_1, y_2 = x_2$ 或 $y_1=y_2=x_1$（退化），需检查出现次数 $\ge 3$ 或 $\ge 4$。 $7$. 若找不到合法的 $y_1, y_2$，输出 NO。 $8$. 否则输出 YES 和四个点的坐标（按 $(x_1,y_1), (x_1,y_2), (x_2,y_1), (x_2,y_2)$ 顺序，任意顺序均可）。

---

正确性说明

• 我们固定 $x_1, x_2$ 为全局最小和最大，因为改变 $x$ 对只会减小 $dx$，从而可能减小面积（除非 $y$ 差能大幅增加，但 $y$ 差受限于候选值范围，不会超过全局次大减次小，而全局次大减次小 $≤$ 全局最大减最小，所以 $dx$ 取最大是最优的）。
• $y$ 的候选我们尝试了可能的最大差值组合，确保面积最大。
• 特殊情况（$m=2,3$）单独处理，避免遗漏。

---

时间复杂度

• 统计频次：$O(n \log n)$（使用 map）或 $O(n)$（使用 unordered_map，但值范围大，可能冲突）。
• 排序：$O(m \log m)$，$m$ 为不同值的数量，$m \le n$。
• 总复杂度 $O(n \log n)$，$n$ 总和 $2\times 10^5$，足够快。

---

完整代码（标程）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        map<long long, int> cnt;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            cnt[a[i]]++;
        }

        vector<long long> cand;
        for (auto& [val, c] : cnt) {
            if (c >= 2) cand.push_back(val);
        }

        if (cand.size() < 2) {
            cout << "NO\n";
            continue;
        }

        sort(cand.begin(), cand.end());
        int m = cand.size();

        long long x1 = cand[0], x2 = cand[m-1];
        long long y1, y2;
        long long dy = -1;

        // try (cand[1], cand[m-2]) if exists
        if (m >= 4) {
            y1 = cand[1], y2 = cand[m-2];
            dy = y2 - y1;
        }
        // try (cand[0], cand[m-1]) if not same as x1,x2 or enough count
        if (x1 != cand[0] || x2 != cand[m-1]) {
            // actually they are same as x1,x2, so need cnt >=3
            if (cnt[x1] >= 3 && cnt[x2] >= 3) {
                long long ndy = x2 - x1;
                if (ndy > dy) {
                    dy = ndy;
                    y1 = x1; y2 = x2;
                }
            }
        }
        // try (cand[0], cand[m-2]) and (cand[1], cand[m-1]) etc for safety
        if (m >= 3) {
            if (cnt[cand[0]] >= 2 && cnt[cand[m-2]] >= 2 && (cand[0] != x1 || cand[m-2] != x2)) {
                long long ndy = cand[m-2] - cand[0];
                if (ndy > dy) {
                    dy = ndy;
                    y1 = cand[0]; y2 = cand[m-2];
                }
            }
            if (cnt[cand[1]] >= 2 && cnt[cand[m-1]] >= 2 && (cand[1] != x1 || cand[m-1] != x2)) {
                long long ndy = cand[m-1] - cand[1];
                if (ndy > dy) {
                    dy = ndy;
                    y1 = cand[1]; y2 = cand[m-1];
                }
            }
        }
        // if m==2
        if (m == 2) {
            if (cnt[x1] >= 4) {
                dy = 0;
                y1 = x1; y2 = x1;
            } else if (cnt[x1] >= 3 && cnt[x2] >= 3) {
                dy = 0;
                y1 = x1; y2 = x2;
            }
        }

        if (dy < 0) {
            cout << "NO\n";
            continue;
        }

        cout << "YES\n";
        // output points: (x1,y1), (x1,y2), (x2,y1), (x2,y2)
        cout << x1 << " " << y1 << " ";
        cout << x1 << " " << y2 << " ";
        cout << x2 << " " << y1 << " ";
        cout << x2 << " " << y2 << "\n";
    }

    return 0;
}

---

示例验证

样例 1

输入：

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

输出：

YES
1 2 1 7 6 2 6 7

面积 = $(6-1) \times (7-2) = 5 \times 5 = 25$，最大。

样例 2

输入：

8
0 0 -1 2 2 1 1 3

输出：

NO

无法构成矩形（候选值 $0,1,2,-1,3$ 出现次数均 $\ge 2$，但最小 $x=-1$，最大 $x=3$，$y$ 候选次小 $0$，次大 $2$，差 $2$，面积 $4\times 2=8$，但检查出现次数：$-1$ 出现 $1$ 次，不可用，所以无合法矩形）。

样例 3

输入：

8
0 0 0 0 0 5 0 5

输出：

YES
0 0 0 5 0 0 0 5

退化矩形，面积 $0$。

---

总结

• 核心：选择最小和最大的数作为 $x_1, x_2$，选择次小和次大的数作为 $y_1, y_2$（若可用）。
• 处理边界情况（$m=2,3$）及出现次数不足的情况。
• 输出任意顺序的四个顶点坐标。