最大矩形面积题解

一、算法思路

本题的核心思路是利用矩形的几何性质：矩形的两条对角线互相平分且长度相等。基于这一性质，我们可以通过以下步骤求解最大矩形面积：

1. 对角线特征提取：对于任意两点构成的线段，将其视为矩形的潜在对角线。记录该线段的三个关键信息：

   • 对角线中点坐标（用 (x1+x2, y1+y2) 表示，避免浮点数精度问题）
   • 对角线长度的平方（避免开方运算，提高效率并保证精度）
   • 构成线段的两个点的索引

2. 对角线分组排序：将所有线段按「长度平方降序」排序（优先检查更长的对角线，可能更快找到最大面积），长度相同的线段按中点坐标排序。这样可以让满足「同中点、等长度」的潜在对角线（即同一矩形的两条对角线）聚集在一起。

3. 矩形验证与面积计算：对于每组「同中点、等长度」的线段，任意两条线段可构成矩形的两条对角线。利用向量叉积的几何意义计算矩形面积：若两条对角线 AC 和 BD 相交于中点，则矩形面积等于 (向量OA × 向量OB) × 2（简化后可通过两点间距离推导）。通过遍历组内线段组合，计算并记录最大面积。

二、完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ldo long double
int n;
int x[1000005], y[1000005], cnt;
struct Edge {
    int x, y, i, j;
    ldo len;
} a[3000005];
bool cmp(Edge x, Edge y) {
    if (x.len != y.len)
        return x.len > y.len;
    if (x.x != y.x)
        return x.x < y.x;
    return x.y < y.y;
}
ldo leng(int i, int j) {
    return ((x[j] - x[i]) * (x[j] - x[i]) + (y[j] - y[i]) * (y[j] - y[i]));
}
void add(int i, int j) {
    a[++cnt].len = leng(i, j);
    a[cnt].x = (x[i] + x[j]);
    a[cnt].y = (y[i] + y[j]);
    a[cnt].i = i;
    a[cnt].j = j;
}
signed main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i ++) {
        for (int j = i + 1; j <= n; j ++) {
            add(i, j);
        }
    }
    sort(a + 1, a + cnt + 1, cmp);
    int maxn = 0;
    for (int i = 1; i <= cnt; i ++) {
        int last = i;
        while (i + 1 <= cnt && abs(a[i + 1].len - a[i].len) < 1e-9 && a[i + 1].x == a[i].x && a[i + 1].y == a[i].y) {
            for (int j = last; j <= i; j ++) {
                int p1 = a[j].i, p2 = a[j].j;
                int p3 = a[i + 1].i;
                ldo dx1 = x[p2] - x[p1], dy1 = y[p2] - y[p1];
                ldo dx2 = x[p3] - x[p1], dy2 = y[p3] - y[p1];
                ldo area = abs(dx1 * dy2 - dx2 * dy1);
                maxn = max(maxn, (int)round(area));
            }
            i ++;
        }
    }
    cout << maxn << endl;
    return 0;
}

三、代码优化说明

1. 精度处理：

   • 对角线长度用平方值存储（leng 函数返回平方和），避免开方导致的精度损失。
   • 比较长度时使用 abs(a[i+1].len - a[i].len) < 1e-9，处理浮点数精度误差。

2. 效率优化：

   • 用 ios::sync_with_stdio(0); cout.tie(0); 关闭同步，加速输入输出。
   • 按长度降序排序，优先处理更长的对角线，可能提前找到最大面积（虽未剪枝，但实际运行中可减少无效计算）。

3. 面积计算优化：

   • 利用向量叉积直接计算面积：对于四点 p1, p2, p3, p4（两条对角线端点），面积等于向量 p1p2 与 p1p3 叉积的绝对值，避免多次开方运算，提高效率和精度。

四、复杂度分析

• 时间复杂度：$O(n^2 \log n)$。其中 $n^2$ 是两点组合的数量（最多 $1500^2=2.25 \times 10^6$ 组），排序复杂度为 $O(n^2 \log n^2) = O(n^2 \log n)$，分组后内部遍历的总复杂度近似 $O(n^2)$（每组内线段数较少）。
• 空间复杂度：$O(n^2)$，用于存储所有两点组合的线段信息，对于 $n=1500$ 完全可行。

该算法在题目给定的 $n \leq 1500$ 数据范围内效率充足，能够快速找到最大矩形面积。