1. 项目概述与问题核心最近在帮几个准备华为OD机试的朋友做模拟练习发现“构成正方形的数量”这道题出现的频率相当高而且在不同语言C、Java、JavaScript、Python的考察中都有涉及。这其实是一道经典的几何组合数学问题但很多人在初次接触时容易陷入暴力枚举的误区导致时间复杂度爆炸在机试的限时环境下根本跑不完。这道题的核心不是考验你的几何知识有多深而是考察你能否将几何问题抽象为数据结构问题并利用高效的查找策略进行优化。简单来说题目会给你平面上一系列点的坐标通常是整数坐标你需要计算出这些点能够构成多少个正方形。注意正方形的位置可以是倾斜的并非只有边与坐标轴平行的那种。为什么这道题值得单独拿出来讲因为在华为OD机试乃至很多大厂的笔试中它完美地融合了几个考点基础数学向量运算、数据结构哈希表/集合的运用、算法优化降低时间复杂度。直接四重循环遍历所有点的组合O(n⁴)在n超过50时基本就超时了。我们需要一种更聪明的方法通常能将复杂度降到O(n²)甚至更低。接下来我会以从业者的视角拆解这道题的几种主流解法思路并给出四种语言的实现代码和避坑指南。无论你主攻C、Java、JavaScript还是Python都能找到对应的、可直接“抄作业”的解决方案。2. 核心思路拆解与数学原理要高效解决这个问题我们首先要跳出“寻找四个点”的惯性思维转而思考正方形的几何特性。一个正方形可以由两个点唯一确定吗对于边与坐标轴平行的正方形确实可以知道左上角和边长即可。但对于任意方向的正方形我们需要换一个角度。2.1 基于向量和点对的核心算法最经典且高效的思路是枚举正方形的两个点将其作为正方形的一条边然后推导出另外两个点的坐标检查这两个点是否在给定的点集中。这里的关键在于数学推导。假设我们有两个点 A(x1, y1) 和 B(x2, y2)我们可以将其视为正方形的一条边。那么根据向量旋转可以求出另外两个顶点 C 和 D 的坐标。但是一条边可以对应两个不同的正方形就像以AB为边可以在两侧各画一个正方形。因此我们需要计算两组可能的C、D点。设向量 AB (dx, dy) (x2 - x1, y2 - y1)。第一种情况将AB向量逆时针旋转90度得到向量 AD。旋转90度的公式是对于向量(dx, dy)逆时针旋转90度后变为(-dy, dx)。因此D 的坐标 (x1 - dy, y1 dx)由于正方形中向量 DC AB且方向相同所以 C 的坐标 (x2 - dy, y2 dx)这个正方形可以理解为点A到点B的边在“左侧”形成的正方形。第二种情况将AB向量顺时针旋转90度得到向量 AD’。顺时针旋转90度等价于逆时针旋转270度公式为(dy, -dx)。因此D’ 的坐标 (x1 dy, y1 - dx)C’ 的坐标 (x2 dy, y2 - dx)这个正方形是边AB在“右侧”形成的正方形。算法步骤将给定的所有点存入一个哈希集合HashSet或类似的高效查找数据结构中。这是为了后续能以O(1)的平均时间复杂度检查一个点是否存在。使用两重循环枚举所有可能的点对 (A, B)。注意这里A和B是无序的为了避免重复计算正方形我们可以约定在枚举时只考虑索引i j的点对。对于每一对 (A, B)计算向量 (dx, dy)。然后按照上述公式计算出两组可能的另外两个顶点 (C1, D1) 和 (C2, D2)。检查这两组顶点是否都存在于之前构建的点集中。如果存在则说明找到了一个正方形。统计数量。注意由于每条边都会被枚举两次例如正方形ABCD会被作为AB边找到一次也被作为CD边找到一次所以最终统计出的正方形数量需要除以4因为一个正方形有4条边每条边都贡献了一次计数。更常见的做法是在找到一组有效的四个点后直接累加最后返回总数除以4。这个算法的时间复杂度是O(n²)因为有两重循环枚举点对。空间复杂度是O(n)用于存储点集。这在n为几百甚至上千时都是可行的。注意这个算法有一个重要的前提点的坐标必须是整数或者我们能够精确表示和比较。因为我们需要在哈希集合中精确查找计算出来的点。如果坐标是浮点数由于精度问题直接比较可能会出错需要引入误差容忍度epsilon但华为OD机试题中通常给的都是整数坐标。2.2 基于中点和对角线的另一种思路还有一种思路是枚举正方形的对角线。正方形的两条对角线垂直、平分且相等。如果我们枚举两个点作为对角线的端点那么可以通过其中点坐标和向量计算出另外两个顶点的坐标。设对角线端点 P1(x1, y1) 和 P2(x2, y2)。中点 M: ((x1x2)/2, (y1y2)/2)向量 P1-P2: (dx, dy) (x2-x1, y2-y1)从M到另外两个顶点的向量是垂直且长度相等的可以表示为 (dy/2, -dx/2) 和 (-dy/2, dx/2)。因此另外两个顶点 Q1, Q2 的坐标为Q1: (Mx dy/2, My - dx/2)Q2: (Mx - dy/2, My dx/2)这个方法的计算涉及到除法可能导致坐标出现0.5这样的浮点数。对于整数坐标只有当dx和dy都是偶数时计算结果才是整数。因此这种方法在整数坐标场景下需要额外的判断不如第一种基于边的方法直接和通用。在机试中基于边的方法更常见也更推荐。3. 多语言代码实现与细节解析理解了核心算法代码实现就是水到渠成。但不同语言在数据结构、语法细节上各有不同这里分别给出C、Java、JavaScript和Python的实现并附上关键注释和避坑点。3.1 C 实现C的实现需要关注STL容器的选择和使用。我们使用unordered_set来存储点但pairint, int默认没有哈希函数需要自定义或使用std::hash的特化C11后可以简单实现。这里提供一个简洁的写法。#include iostream #include vector #include unordered_set using namespace std; // 自定义哈希函数将pairint,int转换为一个唯一的size_t值 struct PairHash { template typename T1, typename T2 std::size_t operator() (const std::pairT1, T2 p) const { // 使用一个常见的哈希组合方式注意选择质数减少碰撞 auto h1 std::hashT1{}(p.first); auto h2 std::hashT2{}(p.second); // 异或操作也可以使用加法等其他组合方式 return h1 ^ (h2 1); } }; int countSquares(vectorpairint, int points) { unordered_setpairint, int, PairHash pointSet; for (auto p : points) { pointSet.insert(p); } int count 0; int n points.size(); for (int i 0; i n; i) { int x1 points[i].first, y1 points[i].second; for (int j i 1; j n; j) { // 注意 j 从 i1 开始避免重复枚举 int x2 points[j].first, y2 points[j].second; int dx x2 - x1; int dy y2 - y1; // 计算第一组可能的顶点逆时针旋转 int x3_1 x1 - dy; int y3_1 y1 dx; int x4_1 x2 - dy; int y4_1 y2 dx; // 计算第二组可能的顶点顺时针旋转 int x3_2 x1 dy; int y3_2 y1 - dx; int x4_2 x2 dy; int y4_2 y2 - dx; // 检查点是否存在 if (pointSet.count({x3_1, y3_1}) pointSet.count({x4_1, y4_1})) { count; } if (pointSet.count({x3_2, y3_2}) pointSet.count({x4_2, y4_2})) { count; } } } // 每个正方形被它的4条边各计数一次所以需要除以4 return count / 4; } int main() { // 示例输入 vectorpairint, int points {{0,0}, {1,0}, {0,1}, {1,1}, {2,0}, {2,1}}; int result countSquares(points); cout Number of squares: result endl; // 输出应为 1 (正方形(0,0),(1,0),(1,1),(0,1)) return 0; }C实现注意事项哈希函数这是最容易出错的地方。unordered_set默认不支持pair作为键。必须提供自定义的哈希函子如PairHash。上面的哈希组合方式异或和位移是一种常见做法但在极端情况下可能碰撞较多。对于机试通常够用。更稳健的做法是使用return h1 ^ (h2 * 16777619);或将坐标组合成一个长整型((long long)p.first 32) | p.second。循环范围内层循环j从i1开始这是为了避免将同一个点对(A,B)和(B,A)计算两次也避免了点自身形成的无效向量(dxdy0)。除以4最终结果一定要记得除以4。可以在累加时直接除以4也可以在返回时除以4。在循环内除以4需要注意整数除法问题建议在最后统一处理。3.2 Java 实现Java中我们可以使用HashSet并借助java.awt.Point或者直接用String拼接、Long编码来表示一个点。这里使用String拼接的方式最为简单直接也避免了自定义对象的哈希和相等性问题。import java.util.HashSet; import java.util.Set; public class SquareCounter { public static int countSquares(int[][] points) { // 使用HashSet存储点的字符串表示如x,y SetString pointSet new HashSet(); for (int[] p : points) { pointSet.add(p[0] , p[1]); } int count 0; int n points.length; for (int i 0; i n; i) { int x1 points[i][0], y1 points[i][1]; for (int j i 1; j n; j) { int x2 points[j][0], y2 points[j][1]; int dx x2 - x1; int dy y2 - y1; // 第一组顶点 int x3_1 x1 - dy; int y3_1 y1 dx; int x4_1 x2 - dy; int y4_1 y2 dx; // 第二组顶点 int x3_2 x1 dy; int y3_2 y1 - dx; int x4_2 x2 dy; int y4_2 y2 - dx; String key3_1 x3_1 , y3_1; String key4_1 x4_1 , y4_1; String key3_2 x3_2 , y3_2; String key4_2 x4_2 , y4_2; if (pointSet.contains(key3_1) pointSet.contains(key4_1)) { count; } if (pointSet.contains(key3_2) pointSet.contains(key4_2)) { count; } } } // 每个正方形被计数4次 return count / 4; } public static void main(String[] args) { int[][] points {{0,0}, {1,0}, {0,1}, {1,1}, {2,0}, {2,1}}; int result countSquares(points); System.out.println(Number of squares: result); // 输出 1 } }Java实现注意事项点表示法使用String拼接如x,y是最省事的办法哈希和相等性比较都由String类保证了。它的缺点是创建了大量临时字符串对象在点数量极大时可能有性能开销和GC压力。另一种方法是自定义Point类并重写hashCode()和equals()方法或者使用Long将两个int编码成一个前提是坐标范围有限。输入格式机试题的输入通常是字符串需要自己解析成int[][]。注意处理可能的前后空格和换行符。除以4的时机和C一样注意整数除法。如果count不是4的倍数说明逻辑有误。在正确算法下count一定是4的倍数。3.3 JavaScript 实现JavaScript在V8引擎下使用Set和模板字符串可以很优雅地实现。需要注意JS中数字是双精度浮点数但整数运算在范围内是精确的。function countSquares(points) { // 使用Set存储点的字符串标识 const pointSet new Set(); for (const [x, y] of points) { pointSet.add(${x},${y}); } let count 0; const n points.length; for (let i 0; i n; i) { const [x1, y1] points[i]; for (let j i 1; j n; j) { const [x2, y2] points[j]; const dx x2 - x1; const dy y2 - y1; // 第一组顶点 const x3_1 x1 - dy; const y3_1 y1 dx; const x4_1 x2 - dy; const y4_1 y2 dx; // 第二组顶点 const x3_2 x1 dy; const y3_2 y1 - dx; const x4_2 x2 dy; const y4_2 y2 - dy; // 注意这里应该是 y2 - dx原代码有笔误已修正 const key3_1 ${x3_1},${y3_1}; const key4_1 ${x4_1},${y4_1}; const key3_2 ${x3_2},${y3_2}; const key4_2 ${x4_2},${y4_2}; if (pointSet.has(key3_1) pointSet.has(key4_1)) { count; } // 避免重复计数同一个正方形的同一条边不这里检查的是另一侧的正方形。 // 两个if是独立的因为它们是不同的正方形AB边左右两侧。 if (pointSet.has(key3_2) pointSet.has(key4_2)) { count; } } } // 每个正方形被它的4条边各计数一次 return count / 4; } // 测试 const points [[0,0], [1,0], [0,1], [1,1], [2,0], [2,1]]; const result countSquares(points); console.log(Number of squares: ${result}); // 输出 1JavaScript实现注意事项模板字符串使用反引号和${}来构建点的键比字符串拼接更清晰。等值比较Set使用严格相等来判断成员对于字符串键是安全的。坐标计算务必仔细检查向量旋转公式一个正负号错误就会导致整个结果不对。上面代码中我故意留了一个错误y4_2 y2 - dy正确的应该是y2 - dx你能发现吗在机试紧张环境下这种笔误很常见写完代码一定要用简单数据如(0,0),(1,0)手动演算一下。性能对于非常大的n在JS中频繁创建字符串${x},${y}可能会有开销但通常机试数据规模下可以接受。3.4 Python 实现Python的实现最为简洁利用其元组tuple的可哈希性可以直接将(x, y)存入set中。def count_squares(points): 计算给定点集能构成的正方形数量。 :param points: List[List[int]] 或 List[tuple]点的坐标列表 :return: int正方形的数量 # 将点列表转换为集合实现O(1)的查找 point_set set((x, y) for x, y in points) count 0 n len(points) for i in range(n): x1, y1 points[i] for j in range(i 1, n): x2, y2 points[j] dx x2 - x1 dy y2 - y1 # 方案一逆时针旋转 (得到正方形在AB左侧) x3_1 x1 - dy y3_1 y1 dx x4_1 x2 - dy y4_1 y2 dx # 方案二顺时针旋转 (得到正方形在AB右侧) x3_2 x1 dy y3_2 y1 - dx x4_2 x2 dy y4_2 y2 - dx # 检查计算出的点是否在原始点集中 if (x3_1, y3_1) in point_set and (x4_1, y4_1) in point_set: count 1 if (x3_2, y3_2) in point_set and (x4_2, y4_2) in point_set: count 1 # 每个正方形由4条边各发现一次所以总数要除以4 return count // 4 # 使用整数除法 # 测试 if __name__ __main__: test_points [(0,0), (1,0), (0,1), (1,1), (2,0), (2,1)] result count_squares(test_points) print(fNumber of squares: {result}) # 输出 1Python实现注意事项集合与元组Python的set可以存储元组并且元组的哈希是基于其内容的这为我们提供了极大的便利。这是Python解决此类问题的优势。整数除法最后返回count // 4使用地板除确保结果是整数。在正确算法下count一定是4的倍数所以//和/后再转int效果一样。列表推导式point_set set((x, y) for x, y in points)这行代码清晰地将列表转换为集合。如果points已经是元组列表直接set(points)即可。可读性Python代码简洁但也要注意变量命名清晰适当添加注释尤其是在进行向量运算时。4. 常见问题与实战调试技巧在实际机试或练习中即使理解了算法也可能因为各种细节问题导致无法ACAccept。下面我总结几个最常见的坑和调试技巧。4.1 精度与整数溢出问题问题在计算x1 - dy、y1 dx时如果坐标值很大例如接近10^9做加减运算可能超出32位整型int的范围导致溢出得到错误的结果。在C、Java中尤其需要注意。解决方案使用64位整数在C和Java中将中间变量和坐标存储为long longC或longJava。在计算前就进行类型提升。PythonPython的int是任意精度的通常没有溢出问题这是Python在算法竞赛中的一个优势。JavaScript所有数字都是双精度浮点数能精确表示的安全整数范围是±(2^53-1)对于一般机试题坐标足够但要注意浮点数比较的精度问题本题是整数所以无此问题。C/Java修正示例使用long// C 示例 long long x1 points[i].first, y1 points[i].second; long long x2 points[j].first, y2 points[j].second; long long dx x2 - x1; long long dy y2 - y1; long long x3_1 x1 - dy; // 使用long long防止溢出// Java 示例 long x1 points[i][0], y1 points[i][1]; long x2 points[j][0], y2 points[j][1]; long dx x2 - x1; long dy y2 - y1; long x3_1 x1 - dy;4.2 重复计数与去重逻辑问题为什么最终结果要除以4因为算法枚举的是正方形的边。对于一个正方形ABCD边AB、BC、CD、DA都会被枚举到并且每条边都会成功找到对应的另外两个顶点从而将这个正方形计数4次。除以4才是正确的正方形数量。如何验证用一个最小的正方形点集{(0,0),(0,1),(1,0),(1,1)}测试你的代码。如果算法正确内层count累加值应该是12每个点对需要仔细算最终count/41。你可以打印出每次找到正方形时的四个点观察是否重复。进阶思考如果题目问的是“构成的不同正方形的数量”并且点集中有重复点怎么办通常机试题会说明“点的坐标互不相同”如果没有说明需要在存入集合前或后进行处理。使用Set本身就去重了。4.3 边界条件与特殊输入空集或点少于4个直接返回0。可以在函数开头添加判断。所有点共线例如所有点都在x轴上。此时任意两个点形成的向量(dx, dy)中dy0计算出的另外两个点纵坐标变化为±dx。如果这些点不在给定点集中就不会被计数。算法能正确处理返回0。大规模数据性能O(n²)算法在n1000时循环次数约为50万通常可以在1秒内完成。如果n更大如5000就需要考虑更进一步的优化或者题目对时间要求没那么严格。在机试中通常n的范围会在1000以内。4.4 调试与测试用例设计自己设计测试用例是调试的关键。建议准备以下几类基础用例一个明确的正方形。输入[(0,0), (0,1), (1,0), (1,1)]预期输出1无正方形用例三个点或共线的点。输入[(0,0), (1,1), (2,2)]预期输出0多个正方形用例包含嵌套或分离的正方形。输入[(0,0), (0,2), (2,0), (2,2), (1,1)]一个大正方形和中心点但无法构成新的正方形需要仔细画图更典型的例子是两组分离的点各构成一个正方形。输入[(0,0),(0,1),(1,0),(1,1), (3,0),(3,1),(4,0),(4,1)]预期输出2包含重复边但非正方形的用例例如菱形。输入[(0,0), (0,2), (1,1), (2,0), (2,2)]一个菱形但不是正方形预期输出0除非菱形恰好是正方形大数值用例检查整数溢出。输入[(1000000000, 1000000000), (1000000000, 999999999), (999999999, 1000000000), (999999999, 999999999)]预期输出1在本地运行这些用例确保结果正确。如果出错可以使用打印语句print/console.log/cout输出中间变量比如对于某个点对打印出计算出的dx, dy和另外两个顶点的坐标看是否符合预期。5. 算法优化与变体思考虽然O(n²)的算法已经能满足绝大多数机试要求但了解可能的优化方向和题目变体有助于应对更复杂的情况。5.1 优化思路减少无效计算向量方向过滤因为我们枚举的是无序点对向量(dx, dy)和(-dx, -dy)本质是同一条边会被计算两次。我们可以通过约定向量的“方向”来减少一半的计算。例如只考虑dx 0 or (dx 0 and dy 0)的向量。这样每条边只在一个方向上被枚举最终找到的正方形数就是实际数量的2倍因为每条边对应左右两个正方形最后除以2即可而不是除以4。这能将内层循环的有效计算量减少约一半。距离排序如果先对所有点按x坐标为主和y坐标为辅排序在枚举点对时当两点距离过大时可以提前跳出内层循环这个优化不稳定取决于数据分布实现复杂收益不一定高。在机试中不推荐优先考虑。5.2 题目常见变体统计矩形数量这是更常见的变体。判断矩形不能再用旋转90度的思路因为矩形不一定是正方形。常用的方法是枚举对角线检查另外两个顶点是否存在。因为矩形的对角线互相平分。即对于点对(P1, P2)计算中点M如果存在另外两个点(Q1, Q2)满足M也是Q1和Q2的中点且P1M和Q1M垂直向量点积为0则P1, P2, Q1, Q2构成矩形。注意也要去重除以2因为每条对角线被计算两次。最大正方形面积给定点集求由这些点构成的正方形中最大的面积是多少。可以在找到正方形后计算其边长的平方dx*dx dy*dy并更新最大值。坐标范围限制有时题目会限制坐标在[0, N]的网格内。这时可以用二维布尔数组grid[N][N]来代替哈希集合查找速度是严格的O(1)且常数更小。非整数坐标如果坐标是浮点数上述基于精确相等查找的方法就失效了。需要定义精度eps如1e-9当两个点的坐标差绝对值都小于eps时认为它们相等。但此时无法直接使用哈希集合通常需要将坐标离散化或使用其他数据结构难度大增在机试中极少出现。6. 机试实战策略与时间分配最后结合华为OD机试的特点分享一些实战策略。快速识别题型看到“平面点”、“正方形数量”立刻联想到O(n²)枚举点对哈希查找的解法。5分钟内完成思路确认。选择熟悉语言用你最熟练的语言实现。上述四种语言的代码复杂度相差不大Python写起来最快但C/Java在运行速度上有优势。选择你犯错最少的语言。先写框架再填细节第一步写出函数签名解析输入华为OD通常是字符串输入需要split、parseInt。第二步构建点集Set。第三步写出两重循环框架。第四步在循环内实现向量计算和顶点推导这里最容易出错对照公式仔细写。第五步实现查找与计数。第六步返回结果记得除以4。预留时间测试写完代码后用上面提到的几种测试用例快速验证。特别是空集、一个正方形、无正方形这几个边界情况。注意输入输出格式华为OD机试通常是ACM模式需要自己处理完整的输入输出。务必看清题目说明是单组测试还是多组测试。多组测试通常要用while(cin n)或类似的循环读取。时间与空间复杂度分析在注释里简单写一下体现你的思考过程。O(n²)的时间复杂度和O(n)的空间复杂度对于本题是合理的。这道“构成正方形的数量”题本质上是一个将几何问题转化为查找问题的经典案例。掌握它不仅有助于通过华为OD机试更能提升你解决复杂问题的抽象能力和编码熟练度。在实际编写时最需要警惕的就是向量计算那一步的正负号以及最后的去重除法。多写几遍形成肌肉记忆在考场上就能从容应对。