企业官网建设流程全解析

看到【数据结构】平行四边形数量这个标题，我第一反应是：这又是一道经典的“披着几何外衣”的数据结构题。很多人在期末考试、考研数据结构真题、或者面试算法题里都遇到过它，题目描述通常只有一句话：给定平面上 n 个点，求这 n 个点能组成多少个平行四边形。别小看这句话，它背后把哈希表、集合映射、组合计数、浮点数精度处理这些数据结构核心知识全串起来了，是一道非常典型的“以数据结构为主、以几何性质为辅”的综合题。

这篇文章我打算直接以一个刷题过来人的视角，把这道题的完整思路、代码实现、复杂度分析、踩坑实录全部拆开来讲。无论是正在准备考研数据结构、还是在刷算法面试题、又或者是期末复习想找一道题吃透哈希表的用法，这篇文章应该都能让你有收获。我会从数学性质讲到哈希函数设计，从 C++ 代码讲到 Python 实现，尽量做到看完就能自己写出来。

1. 一个看似几何的题，为什么会被归到数据结构

1.1 题目到底在问什么

先确认一下题面。给定 n 个二维平面上的点，点的坐标都是整数，要求统计由这些点作为四个顶点能组成多少个平行四边形。注意这里说的是“不同的平行四边形”而不是“不同的顶点组合”，所以如果四个点确定一个平行四边形，它只能被计数一次。

第一次看到这类题，很多人会误以为要用计算几何的模板，比如极角排序、向量叉积、直线扫描之类。但细想一下会发现，计算几何在这道题里只是“背景设定”，真正决定复杂度上限的，是你怎么对这些点做组织和检索。也就是说，这道题考察的核心是数据结构：怎么存、怎么查、怎么避免重复计数。

我在实际刷题群里见过不少同学，一看到“平面点集”就往凸包、旋转卡壳那个方向想，结果越写越复杂。其实这道题最优雅的解法，只需要一个非常朴素的性质：平行四边形两条对角线互相平分。

1.2 换个角度看中点：从几何性质到数据结构设计

平行四边形的判定有很多种，比如两组对边分别平行、一组对边平行且相等、对角线互相平分等等。在这道题里，最合适的是“对角线互相平分”。

为什么？因为“判断两条线段的中点是否相同”这件事，在整数坐标下可以非常精确地完成。设平行四边形的四个顶点是 A、B、C、D，其中 A 和 C 是一条对角线的两个端点，B 和 D 是另一条对角线的两个端点，那么必然满足：

(A.x + C.x, A.y + C.y) == (B.x + D.x, B.y + D.y)

也就是两条对角线的中点坐标相同。

这个性质一旦转化为“若干对点的中点是否相同”，问题就立刻从几何领域切换到了数据结构领域：我们需要枚举所有点对，计算每一个点对的中点，然后统计“具有相同中点的点对有多少个”。如果某个中点出现了 k 次，那么从这个中点出发，任意两条不同的点对都能组成一个平行四边形，因此贡献的组合数为 C(k, 2) = k * (k - 1) / 2。

到了这一步，这道题的核心就完全变成了：如何快速统计大量键值（中点）的出现次数。哈希表就是这个场景下的最优选择。

2. 核心算法思路：枚举点对 + 哈希表统计中点

2.1 暴力枚举为什么不可行

先看最直观的暴力做法：从 n 个点里选 4 个不同点，然后判断这 4 个点能否组成平行四边形。选 4 个点一共有 C(n, 4) 种组合，判断一次需要检查对角线是否互相平分，所以整体复杂度是 O(n^4)。

当 n = 100 时，C(100, 4) 大约是 390 万，勉强能跑；当 n = 500 时，C(500, 4) 大约是 26 亿，直接爆炸；当 n = 2000 时，这个数字是 6.6 万亿，等你跑完比赛都结束了。

我在面试时见过有候选人提出用回溯法枚举四个点再剪枝，这思路本身没错，但剪枝条件在这个场景下很难设计，因为平行四边形没有“方向性”，你提前排掉一个点可能就把正确答案排掉了。所以 O(n^4) 的暴力方案基本只适合作为面试开场白，绝对不适合作为最终答案。

2.2 两条对角线的性质如何变成 O(n²) 的优雅解

优化的突破口在于：不要枚举“四个点”，而是枚举“两条对角线”。任意两条不同的线段，如果它们的中点相同且不共端点，那么这两条线段的四个端点正好组成一个平行四边形。

于是算法流程非常清晰：

1. 枚举所有点对 (i, j)，i < j，计算中点 M(i, j)；
2. 用哈希表统计每个中点被多少条线段共用；
3. 遍历哈希表，对于出现次数为 k 的中点，累加 C(k, 2)。

这样做的时间复杂度是 O(n²)，因为点对数量是 n * (n - 1) / 2，而哈希表的插入和查询平均是 O(1)。

这个复杂度在实际工程里非常可观。n = 5000 时，n² = 2500 万次枚举，C++ 实测大约几百毫秒；n = 10000 时，n² = 1 亿次，依然可以在几秒内跑完。比起 O(n^4) 的暴力，这是质的飞跃。

2.3 中点为什么不直接存浮点：整数二倍中点的妙处

这里有一个关键细节：两个整数相加可能是奇数，除以 2 之后会变成小数。比如点 (0, 0) 和 (1, 1) 的中点是 (0.5, 0.5)，如果直接存浮点数，就需要处理精度问题。

浮点数比较是否有误差？理论上 double 对于 0.5 这种值是可以精确表示的，但如果坐标范围很大，比如 10^9 级别的整数相加，再除以 2，得到的浮点数尾数可能就会有精度损失。在竞赛里这是很致命的：两个数学上相等的中点，因为舍入误差不同，被哈希表判成两个不同的键，结果就少算了。

解决办法很简单：不存中点，存“两倍中点”。也就是对于点 A(x1, y1) 和 B(x2, y2)，直接存(x1 + x2, y1 + y2)。因为坐标都是整数，两个点的横纵坐标相加结果也是整数，不存在精度问题。判断两个点对是否共中点，只需要判断它们的坐标和是否完全相等。

我第一次接触这个技巧时觉得很惊喜，因为它在不引入任何复杂数学的情况下，把一类“浮点精度”问题转换成了“整数哈希”问题，这是数据结构题里非常经典的思维：把不精确的实数域转换到精确的整数域。

3. 完整代码实现：C++ 与 Python 双版本

3.1 C++ 实现：自定义哈希的 unordered_map

C++ 的unordered_map默认不支持pair<int, int>作为键，所以需要自己写哈希函数。这一步很考验基本功，我见过不少人在面试时卡在这里。

一个比较稳妥的哈希写法是把pair<int, int>转换成一个long long，然后直接用标准库的hash<long long>：

#include <bits/stdc++.h> using namespace std; using ll = long long; // 将 pair<int,int> 编码为一个 long long // 注意 x 和 y 可能是负数，要加偏移或者做变换 ll encode(pair<int, int> p) { // 这里假设坐标范围在 [-1e9, 1e9] 之间 // 为了避免负数问题，直接把 int 转成 unsigned int 再拼接 return ((ll)(unsigned int)p.first << 32) | (unsigned int)p.second; } int main() { int n; cin >> n; vector<pair<int, int>> points(n); for (int i = 0; i < n; i++) { cin >> points[i].first >> points[i].second; } // 去重，防止重复点影响结果 sort(points.begin(), points.end()); points.erase(unique(points.begin(), points.end()), points.end()); n = points.size(); unordered_map<ll, int> cnt; cnt.reserve(n * n / 2); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int sx = points[i].first + points[j].first; int sy = points[i].second + points[j].second; cnt[encode({sx, sy})]++; } } long long ans = 0; for (auto &kv : cnt) { long long k = kv.second; ans += k * (k - 1) / 2; } cout << ans << endl; return 0; }

这段代码有几个细节值得展开讲。

第一，encode函数里用(unsigned int)做了无符号转换，目的是防止负数在移位时出现符号扩展的问题。如果你直接对负数做左移，结果是未定义行为，调试起来非常痛苦。

第二，cnt.reserve(n * n / 2)这一步很关键。哈希表在扩容时会重新哈希所有元素，如果不提前预留空间，可能在插入过程中频繁扩容，带来不必要的性能损耗。实测下来，提前 reserve 和不 reserve 在大数据量下能差出 30% 以上的耗时。

第三，为什么要先去重？因为如果输入里有相同的点，那么“一条线段”和“另一条相同位置的线段”会被当成两条不同的点对，导致重复计数。这个问题我在后面的避坑章节会专门展开。

3.2 Python 实现：dict 一把梭

Python 里用字典做这件事非常爽，因为tuple本身就是可哈希的，不需要写自定义哈希函数。

from collections import defaultdict def count_parallelograms(points): # 去重 points = list(set(points)) n = len(points) cnt = defaultdict(int) for i in range(n): xi, yi = points[i] for j in range(i + 1, n): xj, yj = points[j] mid = (xi + xj, yi + yj) cnt[mid] += 1 ans = 0 for k in cnt.values(): ans += k * (k - 1) // 2 return ans n = int(input()) pts = [tuple(map(int, input().split())) for _ in range(n)] print(count_parallelograms(pts))

这个版本非常简洁，核心逻辑不到 20 行。我在带学生的时候经常用这个版本作为“第一次见这道题”的教学版，因为它没有任何额外噪声，能让学生把注意力集中在算法的思路上。

不过要注意，Python 的 O(n²) 枚举在 n 超过 3000 时会比较吃力，主要是因为 Python 的循环速度远不如 C++。如果只是应付面试或者期中期末考试，n 在 2000 以内完全没有问题；但如果是竞赛题给到 n = 10000，还是老老实实用 C++。

3.3 测试用例设计：从正方形到一般图形

写完代码别急着提交，先本地测几个用例。我一般从最简单的图形开始验证。

第一个用例是正方形，四个点分别是 (0, 0), (1, 0), (1, 1), (0, 1)。这个正方形可以组成 1 个平行四边形（也就是它本身）。跑代码结果应该是 1。

第二个用例是矩形，六个点比如 (0, 0), (2, 0), (2, 1), (0, 1), (1, 2), (3, 2)。这个用例比较复杂，我建议先画图手算，再和代码输出对比。矩形 (0,0)-(2,0)-(2,1)-(0,1) 本身有一个平行四边形；再看看 (1,2)-(3,2) 这条线段和哪些线段中点相同……这种人工验证虽然麻烦，但能帮助你真正理解“两条对角线共中点”这句话的含义。

第三个用例是只有两个点，此时没有任何平行四边形，答案是 0。第四个用例是三个点共线，比如 (0,0), (1,1), (2,2)，没有平行四边形，答案是 0。

设计测试用例时，我强烈建议做一次“穷举小规模验证”：随机生成 8 个点，用 O(n^4) 的暴力做对比，再和 O(n²) 的哈希做法比较输出是否一致。这种对拍的方式是竞赛选手的基本功，能瞬间暴露算法里的逻辑 bug。

4. 复杂度、空间优化与工程取舍

4.1 时间空间各花多少，心里得有数

先算复杂度。枚举点对是 O(n²)，每个中点插入哈希表平均 O(1)，所以总时间复杂度 O(n²)。空间复杂度就有点意思了：最坏情况下，每个点对的中点都不同，哈希表里会有 O(n²) 个不同的键，所以空间复杂度也是 O(n²)。

这里有个很容易被忽略的问题：n 稍微大一点，O(n²) 的空间可能比 O(n²) 的时间更先让你崩溃。假如 n = 10000，点对数量接近 5000 万，如果每个键值对在unordered_map里占用 40 字节左右，那光是哈希表就需要近 2 GB 内存，这在比赛环境或者面试的白板环境里都不现实。

时间复杂度和空间复杂度需要一起考虑，这是系统设计的基本素养。我在面试候选人时，如果对方只说出 O(n²) 时间而不提空间，我会接着问一句：“如果 n 很大，你的内存够吗？”这时候能答出“可以改用排序存储”的人，会让我刮目相看。

4.2 内存不够时：排序替代哈希表

哈希表的优势是随机访问 O(1)，代价是每个元素有额外的指针开销。如果程序内存受限，我们可以换一种思路：把所有两倍中点放进一个数组，然后排序，最后对排序后的数组做一次线性扫描，统计相同元素的个数。

这样做的时间复杂度是 O(n² log n)（排序的复杂度），空间复杂度仍然是 O(n²)，但由于使用的是紧凑的vector，单元素开销比哈希表节点小得多，内存占用通常能降低一半以上。

vector<ll> mids; mids.reserve((long long)n * (n - 1) / 2); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int sx = points[i].first + points[j].first; int sy = points[i].second + points[j].second; mids.push_back(encode({sx, sy})); } } sort(mids.begin(), mids.end()); long long ans = 0; long long k = 1; for (size_t i = 1; i < mids.size(); i++) { if (mids[i] == mids[i - 1]) { k++; } else { ans += k * (k - 1) / 2; k = 1; } } ans += k * (k - 1) / 2; cout << ans << endl;

这段排序版本的好处不仅在于内存紧凑，还在于 cache 友好。vector是连续内存，排序时访问局部性很好；而unordered_map的节点是散落在堆上的，遍历时会频繁发生 cache miss。实测在 n = 5000 时，排序版本甚至可能比哈希表版本更快。

这个取舍很有代表性：哈希表和排序是数据结构里两个最基础的工具，它们在不同的约束条件下各有优势。做题时一定要先评估数据范围，再决定用哪个。

4.3 答案数量级估算与 long long 的自觉

很多新手在累加答案时用 int，结果直接溢出。

我们来估算一下答案的最大值。假设 n 个点两两组合出 C(n, 2) 条线段，如果这些线段的中点全部相同，那么 k = C(n, 2)，答案 = C(k, 2)，也就是 C(n,2) * (C(n,2) - 1) / 2。当 n = 2000 时，C(n,2) 约等于 2 × 10^6，答案量级约为 2 × 10^12，int 最大只有约 2.1 × 10^9，所以用 int 必炸，必须用 long long。

在 C++ 里，我习惯把涉及计数的变量统统声明为long long，虽然看起来保守，但能免去无数半夜调 bug 的痛苦。Python 没有这个烦恼，因为它的 int 是任意精度的。

5. 实战中的坑与排查实录

5.1 重复点必须先处理

这是我踩过最深的一个坑。

有一道类似的题目，输入数据里允许出现相同的点。我当时没有去重，结果发现答案比标准答案大很多。原因是这样的：假设输入有 A 和 A' 两个相同点，那么线段 AA' 的长度为 0，中点是 A 本身；但它也可以和其他点组成“退化”的线段。更麻烦的是，相同点会让“四个顶点”的集合出现重复元素，最终导致同一个平行四边形被按多种方式重复计数。

解决办法是在读入之后立刻去重。C++ 里sort加unique，Python 里set直接去重。这个操作是 O(n log n) 的，完全不影响整体复杂度。

去重之后题目实际上变成“给 n 个互不相同的点”，这通常也是很多题面里隐含的默认条件。如果你在面试时发现题面没说，主动问一句“输入点会有重复吗”，是一个很好的加分项。

5.2 四点共线的退化情况怎么办

这个坑更深，也更隐蔽。

比如四个点 (0, 0), (1, 1), (2, 2), (3, 3) 都在同一条直线上。线段 (0,0)-(3,3) 的中点是 (1.5, 1.5)，线段 (1,1)-(2,2) 的中点也是 (1.5, 1.5)。按照我们的算法，这两个点对会被组合成一个“平行四边形”，但实际上四个点都在一条直线上，构不成任何平行四边形。

这就是经典的四点共线退化情况。那么问题来了：如果题面没有保证“无三点共线”，我们的算法就是错的。

怎么处理？常见做法有两种。第一种，在统计答案时判断一下四点是否共线，这会让代码复杂很多；第二种，提前检查输入点集中是否存在三点共线的情况，如果存在，要么题目会特殊说明“共线不算”，要么就把这些点排除掉。但严格来说，最稳妥的方法是做题前先读清楚数据范围：很多竞赛题会直接给出“任意三点不共线”的约束，此时这个坑根本不存在。

如果是面试场景，我建议你主动向面试官确认这个边界条件。因为面试官往往在意的是你能不能在抽象层面把问题建模清楚，而不是真的逼你在白板上写一个共线性判断模块。

5.3 哈希函数写不好，面试直接翻车

C++ 里pair<int,int>不能直接作为unordered_map的键，必须自定义哈希。这个点看起来简单，实际写起来门道不少。

错误示范是把两个 int 异或起来，比如return a.first ^ a.second;。这样会导致大量点对映射到同一个哈希桶，哈希表退化成链表，复杂度从 O(1) 退化成 O(k)。如果 k 很大，整体复杂度就从 O(n²) 退化成了 O(n³)。

正确做法是先把pair<int, int>编码成 64 位整数，再交给自己信任的标准哈希函数。我习惯用：

struct pair_hash { size_t operator()(const pair<int, int>& p) const { return ((size_t)((unsigned int)p.first) << 32) | (unsigned int)p.second; } };

这样每一对整数都能得到一个几乎不冲突的哈希值，实测稳定。记住，写哈希函数时宁可“土”一点，也不要为了花哨而引入碰撞风险。

5.4 计数怎么验证：为什么平方和公式不多不少

最后验证一下计数公式。以正方形四个顶点为例，(0,0), (1,0), (1,1), (0,1)。枚举所有点对，得到六条线段，其中两条对角线分别是 (0,0)-(1,1) 和 (1,0)-(0,1)，它们的中点都是 (1,1)（两倍中点表示）。所以这个中点的出现次数 k = 2，C(2, 2) = 1，答案正好为 1。

再看一个稍微复杂的情况，如果把正方形每条边的中点也算成新的点，那么整个图形变成一个“风车”一样的图形。这个时候可能有多个平行四边形，你可以手算一遍，再用代码验证。如果手算结果和代码输出对不上，多半是你对“不同平行四边形”的定义理解有偏差，或者代码里的去重逻辑有问题。

在做对拍验证时，我通常会把 O(n⁴) 的暴力代码写出来，用随机数据跑几百次，让两个代码的结果完全一致后才算放心。这个习惯救过我很多次，每次都觉得“这么简单的题不可能写错”，结果一测就发现边界情况漏了。

6. 从平行四边形到更多几何计数问题

6.1 如果统计的是矩形呢

平行四边形计数是很多几何计数问题的基础版本。如果题目改成统计矩形，只需要在“中点”这一个维度上再加一个“对角线长度”的约束。

具体来说，矩形的充要条件也是对角线互相平分且相等。所以流程变为：枚举点对，计算中点和线段长度的平方（为了避免浮点，直接用距离平方），然后用一个哈希表去重。对于每个“中点 + 长度”的组合，如果出现 k 次，就累加 C(k, 2)。这样统计出来的就是矩形的数量。

我当时在面试里遇到过一个变体，要求统计正方形数量，那就更简单了，因为正方形还要求两条对角线长度相等。实际上，统计正方形和统计矩形的代码几乎一模一样，只是判断条件多一个。这个扩展能帮你把哈希表的应用理解得更通透。

6.2 如果统计的是菱形呢

统计菱形会比矩形难一些。菱形的特征是“对角线互相垂直且互相平分”，所以你的中点和“向量中点”还需要再满足一个垂直条件。

一般解法是：枚举点对，记录中点，同时记录线段方向向量 (dx, dy)，然后检查“方向向量的点积为 0”的两条线段是否共享中点。这本质上是在做向量之间的垂直关系查找，哈希表的键值结构也会更复杂。

这种一层套一层的题目在竞赛里特别常见，它考察的是你能否把几何判定条件转化为几个“可哈希的原子属性”的组合。一旦你掌握了这种转化方式，就能举一反三。

6.3 这类题在面试、考研和竞赛中的位置

从数据结构知识图谱来看，这道题覆盖了哈希表、组合计数、排序去重三大块知识。考研数据结构里，哈希表的应用题频率一直很高，而这道题恰好是把哈希表的“键值设计”考到了极致：你需要自己设计 key 的类型和哈希函数，还得理解为什么 key 要设计成两倍中点。

竞赛场景下，这道题的模板性也很强。区域赛里经常出现“点集计数”类的题目，核心往往都是某种几何性质 + 哈希表/排序。刷透平行四边形计数，等于掌握了一大类问题的通法。

面试场景就更不用说了。我在模拟面试时经常用这道题考察候选人：题目简单到用一句话就能说清，但深挖下去会牵扯出内存、哈希冲突、浮点精度、边界情况、复杂度权衡这么多东西，非常能反映候选人的代码功底和系统思维。

7. 我的一些个人经验与建议

说点实在的。我第一次做这道题时，犯的错误是直接沿用“暴力枚举四个点”的思路，然后剪枝，折腾了半天还是 O(n^4)，直到看到别人题解里“枚举对角线”这个点才恍然大悟。后来我用这道题给学生讲哈希表，几乎每次都会强调：数据结构题的关键不在“背模板”，而在“找到那个可以把复杂问题简化成键值统计的数学性质”。

还有一个小技巧：写代码之前，先在白纸上把测试用例画出来。几何类题目非常容易在抽象代码里迷失方向，画图能让你对“哪两条线段能构成平行四边形”有直观感知，写代码时自然不容易出错。

如果你在准备期末考试，我建议把这道题的完整代码亲手敲一遍，然后改一改：先改成统计矩形，再改成统计正方形。每一步改动都逼着你去思考“哈希键值需要增加哪些维度”，这才是真正锻炼数据结构思维的方式。光看不写，永远体会不到“把几何性质变成哈希键”的那个瞬间。