企业官网建设流程全解析

1. 这道题到底在考什么

刷题刷到一定阶段，很多人会开始碰几何题。LeetCode 963 的 Minimum Area Rectangle II 就是一道很适合拿来检验“几何性质 + C 语言实现功底”的题。题面本身不复杂，给定一组二维坐标点，要找出能构成矩形的四个点，并返回最小面积；如果不存在任何矩形，返回 0。乍看像是一道普通枚举例题，但里面塞满了让 C 程序员头疼的东西：中点可能是小数、对角线长度可能是无理数、返回值是 double，还得和浮点精度作斗争。

double minAreaFreeRect(int** points, int pointsSize, int* pointsColSize)，这个free值得画重点：矩形可以任意旋转，不要求边和 x/y 轴平行。坐标都是整数，但函数接口是 double，所以我们不能抱着“最后直接返回 int”的心态去写，所有几何计算都得按浮点来对待。点最多 50 个，坐标范围从 -40000 到 40000，这些边界条件决定了我们后面所有数据类型的选择。

1.1 先搞清题面在问什么

输入是 N 个二维点，例如points = [[1,1],[0,0],[2,1],[1,0],[1,2],[0,1]]，输出 2.0；如果给的是[[0,0],[1,0],[0,1],[1,1]]，输出 1.0；如果给的四个点在同一条直线上，就构不成矩形，需要继续搜或者返回 0。注意矩形不一定是“正”的，可以旋转，所以不能用“找一对水平点、再找一对竖直点”的思路。

有的读者可能觉得 50 个点，四重循环也就是 23 万次判断，直接枚举四个点不就完了么？确实能跑完，但麻烦在于你怎么判断“这四个点是不是矩形”。最直觉的做法是量六条距离，看看是不是“两两相同 + 对角相等”，或者检查四个向量两两垂直，这些都要处理浮点、平方根、以及大量分支。这个题真正的价值，是逼你找到一个更稳定的几何判据，把矩形判定变成一个可哈希、可排序的 key。这也是第二题和第一题最不一样的地方。

1.2 为什么说“II”比第一题难一个台阶

第一题的矩形边被限定成与坐标轴平行，在这种简化条件下，可以用“按 x 坐标或 y 坐标先分组再找对边”的办法，甚至可以直接用哈希表把每一条水平边记录下来。第二题一放开旋转，很多偷懒手段就失效了。我把差异列在下面，这样比较清楚：

所以第二题不是第一题的简单加强，而是思路上的切换：从“按坐标分组”变成“按几何不变量分组”。这个不变量就是矩形的两条对角线：它们的中点重合，长度相等。

我自己做这题时的体会是，几何题里“不变量”选对了，代码就顺了。这比纠结哈希函数怎么设计都重要。

2. 核心思路：用两条对角线把所有矩形一次性捞出来

2.1 矩形的最强判定条件

在平面几何里，一个四边形是矩形的充分必要条件是：它的两条对角线长度相等，并且互相平分。反过来想，只要有两个不同的点对，它们的中点重合，并且两个点对的距离相等，这四个点就一定是一个矩形。

为什么一定？两个点对的中点重合，说明以这两条连线为对角线的四边形是平行四边形；对角线长度相等，说明这个平行四边形是矩形。严格证明不复杂，但做题时记住结论就够了。

这个判据的好处是彻底告别“判断四条边是否垂直”这种浮点操作。中点相同属于坐标比较，长度相等属于距离比较，两者都可以用 64 位整数精确表达，剩下唯一的浮点出现在最后算面积那一步。从计算量上看，我们也不需要把所有点对组合都过一遍，而是先把所有点对表示的“对角线”存在一个统一的结构里，再按 key 分组，组内任意两个不同的对角线就可以配成一个候选矩形。

2.2 面积公式：一次叉积算出矩形面积

对候选的两条对角线，设它们的向量分别是 d1 和 d2。四个顶点以中点为原点来看，其实就是两个互为相反数的向量 u 和 -u，以及另一组 w 和 -w。面积可以直接写成2 * |u × w|。由于我们存储的 d1 是一条对角线端点到另一端点的向量，也就是d1 = -2u，d2 = -2w，所以：

• cross(d1, d2) = (-2u) × (-2w) = 4 * (u × w)
• 矩形面积 =2 * |u × w| = |cross(d1, d2)| / 2

这个推导很关键，它告诉我们不要试图把对角线长度 sqrt 出来然后去算，也别被“矩形面积 = 长 × 宽”带偏。用对角线的叉积直接除 2，出来就是精确的矩形面积。而且 cross 本身是整数，在 double 里做一次除以 2 的操作，完全不会出现乱七八糟的近似误差。

2.3 整体算法流程

从实现角度，流程可以分成四步：

1. 两重循环枚举所有点对i < j，对每个点对生成一条记录：两倍中点坐标(x1+x2, y1+y2)、向量差(x2-x1, y2-y1)、长度平方len2。
2. 把所有记录按(两倍中点x, 两倍中点y, len2)排序。排序的好处是 C 语言里不用手写哈希表，相同 key 的记录会自然聚在一起。
3. 扫描排序后的数组，找到相同 key 的连续区间。区间内如果至少两条记录，就两两配对，用叉积求面积。
4. 记录最小非零面积；如果从头到尾没有任何候选，返回 0。

为什么排序而不是哈希？纯粹从工程角度：哈希表在 C 语言里要自己处理冲突、扩容、结构体比较，代码量大，而这道题的点对总数只有n*(n-1)/2，最多 1225 条记录，排序的成本可以忽略。我的习惯是，数据量小到排序能全覆盖的时候，优先排序，代码可读性好很多。这一点在后面还会展开。

3. C 语言实现：排序分组法

3.1 数据结构设计

先定义一条“对角线记录”：

typedef struct { long long mx; // 两倍中点坐标：x1 + x2 long long my; // 两倍中点坐标：y1 + y2 long long len2; // 对角线长度平方 long long dx; // 对角线向量 x 分量，x2 - x1 long long dy; // 对角线向量 y 分量，y2 - y1 } Diag;

有人会问，为什么mx不写成(x1+x2)/2？因为一旦除 2，奇数坐标求和就会出现.5，我们还得拿浮点去比较，完全没必要。直接存x1+x2，相当于是两倍中点，所有比较都变成整数精确比较。两倍中点本身不会溢出：坐标差最大值是 80000，x1+x2范围是 [-80000, 80000]，long long 绰绰有余。

dx和dy是端点之间的向量差，范围也在 [-80000, 80000]。len2是dx*dx + dy*dy，最大值约80000² * 2 = 1.28e10，这个值已经超过 32 位 int 的上限，所以必须用 long long。

3.2 排序规则怎么定

排序比较器按 key 的三个字段依次比较，先中点 x、再中点 y、最后长度平方。因为len2相同时，对角线长度就相同，没必要再比较dx、dy。比较函数直接返回 -1 或 1，避免用a-b这种写法导致 long long 溢出。

static int cmpDiag(const void *a, const void *b) { const Diag *p = (const Diag *)a; const Diag *q = (const Diag *)b; if (p->mx != q->mx) return p->mx < q->mx ? -1 : 1; if (p->my != q->my) return p->my < q->my ? -1 : 1; if (p->len2 != q->len2) return p->len2 < q->len2 ? -1 : 1; return 0; }

3.3 完整 C 代码

下面这段代码可以直接在本地编译器里跑通，也适配在线评测的函数签名。

#include <stdlib.h> typedef struct { long long mx; long long my; long long len2; long long dx; long long dy; } Diag; static int cmpDiag(const void *a, const void *b) { const Diag *p = (const Diag *)a; const Diag *q = (const Diag *)b; if (p->mx != q->mx) return p->mx < q->mx ? -1 : 1; if (p->my != q->my) return p->my < q->my ? -1 : 1; if (p->len2 != q->len2) return p->len2 < q->len2 ? -1 : 1; return 0; } double minAreaFreeRect(int** points, int pointsSize, int* pointsColSize) { (void)pointsColSize; if (pointsSize < 4) return 0.0; int n = pointsSize; int total = n * (n - 1) / 2; Diag *arr = (Diag *)malloc((size_t)total * sizeof(Diag)); if (arr == NULL) return 0.0; int cnt = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long long x1 = points[i][0], y1 = points[i][1]; long long x2 = points[j][0], y2 = points[j][1]; arr[cnt].mx = x1 + x2; arr[cnt].my = y1 + y2; arr[cnt].dx = x2 - x1; arr[cnt].dy = y2 - y1; arr[cnt].len2 = arr[cnt].dx * arr[cnt].dx + arr[cnt].dy * arr[cnt].dy; cnt++; } } qsort(arr, (size_t)cnt, sizeof(Diag), cmpDiag); double best = 0.0; int i = 0; while (i < cnt) { int j = i + 1; while (j < cnt && arr[j].mx == arr[i].mx && arr[j].my == arr[i].my && arr[j].len2 == arr[i].len2) { j++; } if (j - i >= 2) { for (int a = i; a < j; a++) { for (int b = a + 1; b < j; b++) { long long cross = llabs(arr[a].dx * arr[b].dy - arr[a].dy * arr[b].dx); if (cross == 0) continue; double area = (double)cross / 2.0; if (best == 0.0 || area < best) { best = area; } } } } i = j; } free(arr); return best; }

3.4 关键步骤解读

这段代码不长，但有几个地方必须展开说明。

第一，为什么mx = x1 + x2而不是(x1 + x2) / 2。一旦用/，-40000 和 39999 这样的组合会得到 -1，而不是 -0.5；虽然相对关系可能没变，但很容易在细节上埋雷。直接用和，所有比较都精确，不会产生歧义。

第二，为什么len2用平方和而不是sqrt。因为两条对角线长度相等，只需要平方和相等。多存一个整数len2，就避免了求平方根。对角线长度本身可能是无理数，但我们从头到尾都不需要真的去算它。

第三，为什么只枚举i < j。因为一条对角线反着存会产生两条 key 完全相同的重复记录，组内两两配对时会出现“同一个对角线和自己的镜像配对”，导致把同一对点当成矩形来算。i < j可以保证每个无序点对只出现一次。

第四，为什么跳过cross == 0。如果两条对角线向量共线，说明四个点退化成一条直线。比如一条直线上取四个对称分布的点，它们可能满足“中点相同 + 距离相等”，但这不是矩形，面积为 0。如果把它算进结果，best会被 0 污染，后面遇到真正的矩形也没法更新。所以一旦发现共线，直接跳过。

4. 踩坑复盘：这些错我在本地和评测机上都没少犯

写这道题的时候，我先是照着第一题的思路走，后来又尝试了哈希表版本，来回改了几轮才摸清楚哪些地方最容易翻车。下面按踩坑的典型顺序说，希望你能少走一段弯路。

4.1 中点的浮点陷阱

第一次写这题，很多人会先定义一个double mx = (x1 + x2) / 2.0，然后用 double 做结构体成员和哈希 key。这听起来没什么，实际上全是雷：一方面，浮点计算路径不同可能带来尾数差异；另一方面，在哈希表里拿浮点数当 key，任何平台相关的舍入都会让相同的几何意义映射到不同槽位。最好的办法就是永远不要用浮点当 key，整数化的手段就是x1 + x2再加len2，两个都是整数，比较起来干净利落。

4.2 溢出不是“可能”，是“一定”

坐标范围是 [-40000, 40000]。两点间横纵坐标差最多 80000，平方是 6.4e9，两个坐标平方和是 1.28e10，已经超过 32 位 int 的 2147483647。如果dx和dy还是 int，dx * dx会先按 32 位溢出，然后得到的len2完全不可信。差一点点的平方距离都可能导致两个本应同组的点对分到不同组，然后漏掉正确答案。所以真正写代码时，所有坐标和距离相关的字段都应该用 long long，不要觉得 int 够用。

4.3 面积公式的“多乘 / 少乘 / 二”

有段时间我脑子里老想着area = sqrt(len2) * sqrt(len2) / 2，因为对角线长度平方就是 len2，于是想当然地写成len2 / 2，这个算式只有在正方形时才成立。非正方形的矩形，对角线夹角不是 90 度，面积并不是对角线长度平方的一半。正确做法是直接从两条对角线向量的叉积得到面积，cross / 2才是通用的。别绕到边长去，否则你会在几何公式上空耗很久。

4.4 为什么最终选择排序而不是哈希表

用排序分组之后，代码量大约只有哈希表版本的三分之一。哈希表版本还要额外处理 key 的三元组合并成一个整数的问题：三个 long long 字段拼成一个 hash 值，C 语言没有内置的 pair/tuple，你得自己写hash = ...，再解决碰撞，还得考虑是否用拉链法。对这道题来说，点对最多 1225 条，哈希表的中位数查找优势完全发挥不出来。排序是更朴素、更不易写错的选择。如果数据量到十万级别，我可能会反过来用哈希表，但这里完全没必要。

4.5 退化情况和自测用例

写完后跑几个自测用例很有必要：

• [[0,0],[1,1],[2,2],[3,3]]：全部共线，没有矩形，要返回 0。
• 只有三个点：直接返回 0，因为没有四个点组成矩形。
• 一个带多个候选矩形的例子：[[0,0],[2,0],[1,1],[1,-1],[3,3]]，要能挑出最小面积。

尤其要测共线场景。如果代码里没跳过cross == 0，共线点对会算出一个 0，导致best永远停在 0，正好把这个 bug 暴露出来。这种退化情况在官方样例里不一定覆盖，但自己一定要补上。

5. 复杂度分析与扩展思考

5.1 这个复杂度够不够快

枚举所有点对是O(n^2)，生成记录数是n*(n-1)/2，在n = 50时只有 1225 条，排序这部分非常轻松。分组后组内两两配对，理论最坏情况不超过所有点对之间两两组合，也就是大约 75 万次叉积运算，对现代 CPU 来说是毫秒级的事情。所以这个算法的时间和空间都完全满足题目限制。

有些题解会强调哈希表版本能做到平均O(n^2)，但在这个数据范围下，排序分组法的常数更小，代码更短。复杂度分析不是只能用大 O 说话，还要结合数据规模去判断哪种实现更务实。

5.2 从第一题到第二题的迁移套路

第一题 Minimum Area Rectangle 要求边与坐标轴平行，可以用哈希表记录横坐标或纵坐标来做；第二题一旋转，很多“取巧”的方法就失效了，只能回到矩形的本质性质：对角线等长且互相平分。这个套路其实可以推广到一类几何题：

• 找平行四边形：只看中点相同，不需要长度相等，组内两两配对即可；
• 找菱形：中点相同 + 两对角线互相垂直，可以用向量点积判断；
• 找正方形：中点相同 + 对角线等长 + 对角线垂直，三个条件一起上。

换句话说，这道题的核心价值不是让你背一个面积公式，而是让你学会把图形的几何性质转化成可以比较、排序、哈希的整数 key。一旦你习惯这种转化方式，再遇到“任意旋转的图形匹配”问题，第一反应就不是去硬算边长，而是找图形的不变量。

5.3 后续可以怎么扩展

如果你想把这类题练透，可以自己造一点变体：比如输入点集变成浮点坐标，面积要求保留五位小数；或者把“矩形”换成“平行四边形”，问最小面积；又或者要求找面积最大的矩形。这些变体的难点都绕不开同一件事：如何在精度可控的前提下，快速判断一组点是否满足某个几何关系。

我个人在实际操作中的体会是，C 语言做几何题，第一原则就是“能整数就别浮点，能平方就别开根”。这道题的mx = x1+x2、len2 = dx*dx + dy*dy就是这两个原则最典型的体现。把小数换成整数键、把平方距离换成 long long 之后，整个代码的稳定性和可读性都会上一个台阶。如果你也打算用 C 刷几何题，建议先把这个思路吃透，再去看那些花哨的哈希优化，你会觉得顺很多。