题解

我们可以将问题转化为将排序后的数组分成两组，每组 n 个数字，分别作为 x 坐标和 y 坐标。注意，由于每个二元组内可以任意分配（即可以交换 x 和 y），问题等价于下面两种情况中的最优解：

1. 【情况一】

• 直接将排序后数组的前 n 个数作为一组，后 n 个数作为另一组。
• 记排序后的数组为 s[0], s[1], …, s[2n–1]。
• 那么一组的范围为 s[n–1] – s[0]，另一组的范围为 s[2n–1] – s[n]。
• 矩形面积为：
      面积1 = (s[n–1] – s[0]) × (s[2n–1] – s[n])

2. 【情况二】

• 如果把数组中最小的数 s[0] 和最大的数 s[2n–1] 分到同一组，那么另一组必定取自中间部分。
• 不难证明，对于 i 从 1 到 n–1，可以考虑让另一组的最小范围为 s[i+n–1] – s[i]。
• 此时另一维的范围固定为 s[2n–1] – s[0]，矩形面积为：
      面积2 = (s[2n–1] – s[0]) × (s[i+n–1] – s[i])
• 取所有 i 中的最小值，即令
      面积2 = (s[2n–1] – s[0]) × min{ s[i+n–1] – s[i] | 1 ≤ i ≤ n–1 }

代码

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> arr(2 * n);

  // 输入数组
  for (int i = 0; i < 2 * n; i++) {
      cin >> arr[i];
  }

  // 排序
  sort(arr.begin(), arr.end());

  // 计算直接分配的面积
  int ans = (arr[n - 1] - arr[0]) * (arr[2 * n - 1] - arr[n]);

  // 枚举其他可能的分配方式
  for (int i = 1; i < n; i++) {
      ans = min(ans, (arr[2 * n - 1] - arr[0]) * (arr[i + n - 1] - arr[i]));
  }

  cout << ans << endl;
  return 0;
}

python

def main():
    n = int(input())  # 读入n
    arr = list(map(int, input().split()))  # 读入2n个数字

    # 排序
    arr.sort()

    # 计算直接分配的面积
    ans = (arr[n - 1] - arr[0]) * (arr[2 * n - 1] - arr[n])

    # 枚举其他可能的分配方式
    for i in range(1, n):
        ans = min(ans, (arr[2 * n - 1] - arr[0]) * (arr[i + n - 1] - arr[i]))

    print(ans)

if __name__ == "__main__":
    main()

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[2 * n];

        // 输入数组
        for (int i = 0; i < 2 * n; i++) {
            arr[i] = sc.nextInt();
        }

        // 排序
        Arrays.sort(arr);

        // 计算直接分配的面积
        int ans = (arr[n - 1] - arr[0]) * (arr[2 * n - 1] - arr[n]);

        // 枚举其他可能的分配方式
        for (int i = 1; i < n; i++) {
            ans = Math.min(ans, (arr[2 * n - 1] - arr[0]) * (arr[i + n - 1] - arr[i]));
        }

        System.out.println(ans);
    }
}

题目描述

小红拿到了一个长度为2n的数组，她希望把数组中的元素分成$n$个二元组:$(x_i,y_i)$。

每个二元组对应平面直角坐标系的一个点，然后小红希望用一个边和坐标轴平行的矩形将所有点囊括在内。小红希望最终矩形的面积尽可能小，你能帮帮他吗?

输入描述

第一行输入一个正整数n。

第二行输入2n个正整数$a_i$，代表数组的元素 $1\le n\le 10^5$

$1 ≤ a_i \le 10^9$

输出描述

一个整数，代表矩形的最小面积。

样例

输入

2
1 2 3 4

输出

1

说明

$(1,4)$和$(2,3)$