CF 1012A

题目内容

给定 $2 n$ 个数 $a_{1}, a_{2}, \dots, a_{2 n}$ ，现可任意将其组合为 $n$ 对二维欧几里得平面上的坐标 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots ， (x_{n}, y_{n})$ ，这 $n$ 对坐标被一个矩形完全覆盖，试求该矩形的最小面积。

解法

解答

转化题意为将 $2 n$ 个数划分为两个等长序列 $X$ 与 $Y$ ，分别代表所有的 $x$ 坐标与所有的 $y$ 坐标，则答案为 $X$ 的极差乘 $Y$ 的极差的最小值。

考虑如何划分才能最小化该乘积，由于序列中的所有元素都会在 $X$ 或 $Y$ 中出现且仅出现一次，不妨将序列由小到大排序，讨论原序列的最小值 $a_{1}$ 与最大值 $a_{2 n}$ 分别在同一个序列与不同序列的情况：

若在不同序列中，则答案为 $(a_{n} - a_{1}) \times (a_{2 n} - a_{n + 1})$ 。
若在同一序列中，不妨设其均在 $X$ 中，则枚举所有的 $i \in [2, n - 1]$ ，考察若 $Y = {a_{i}, a_{i + 1}, \dots, a_{i + n - 1}}$ 时的答案 $(a_{2 n} - a_{1}) \times (a_{i + n - 1} - a_{i})$ 。

时间复杂度 $O (n \log n)$ 。

AC 代码

见提交记录。