2025 B卷 100分 題型

本文涵蓋詳細的問題分析、解題思路、代碼實現、代碼詳解、測試用例以及綜合分析；
并提供Java、python、JavaScript、C++、C語言、GO六種語言的最佳實現方式！

本文收錄于專欄：《2025華為OD真題目錄+全流程解析/備考攻略/經驗分享》

華為OD機試真題《構成正方形的數量》：

---

---

題目名稱：構成正方形的數量

---

• 知識點：幾何算法、邏輯處理
• 時間限制：1秒
• 空間限制：256MB
• 限定語言：不限

---

題目描述

輸入 N 個互不相同的二維整數坐標，求這 N 個坐標可以構成的正方形數量。（若兩個向量的內積為零，則這兩個向量垂直）

輸入描述

• 第一行為正整數 N，表示坐標數量（1 ≤ N ≤ 100）。
• 后續 N 行每行為坐標 x y，以空格分隔，x、y均為整數（-10 ≤ x, y ≤ 10）。

輸出描述

• 輸出可構成的正方形數量。

示例1
輸入：

3  
1 3  
2 4  
3 1  

輸出：

0  

說明：3個點無法構成正方形。

示例2
輸入：

4  
0 0  
1 2  
3 1  
2 -1  

輸出：

1  

說明：4個點可構成一個正方形。

---

Java

問題分析

我們需要根據輸入的N個二維坐標點，計算能構成的正方形數量。正方形的判定條件是四個點滿足特定的幾何條件：四條邊長度相等，相鄰邊垂直。

解題思路

1. 輸入處理：讀取所有坐標點，并存入集合以便快速查找。
2. 遍歷所有點對：對于每兩個點，計算可能的另外兩個點是否存在。
3. 幾何條件驗證：通過向量旋轉確定可能的另外兩個點，并檢查是否存在。
4. 去重處理：將找到的正方形的四個點排序后生成唯一標識，避免重復統計。

代碼實現

import java.util.*;class Point {int x, y;public Point(int x, int y) {this.x = x;this.y = y;}// 重寫equals和hashCode方法，確保正確比較點@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Point point = (Point) o;return x == point.x && y == point.y;}@Overridepublic int hashCode() {return Objects.hash(x, y);}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();List<Point> points = new ArrayList<>();Set<Point> pointSet = new HashSet<>();// 讀取所有點并存入集合for (int i = 0; i < n; i++) {int x = scanner.nextInt();int y = scanner.nextInt();Point p = new Point(x, y);points.add(p);pointSet.add(p);}Set<String> squares = new HashSet<>();// 遍歷所有點對for (int i = 0; i < points.size(); i++) {Point p1 = points.get(i);for (int j = 0; j < points.size(); j++) {if (i == j) continue; // 跳過同一個點Point p2 = points.get(j);// 計算向量差int dx = p2.x - p1.x;int dy = p2.y - p1.y;// 情況1：計算可能的另外兩個點Point p3 = new Point(p2.x - dy, p2.y + dx);Point p4 = new Point(p1.x - dy, p1.y + dx);// 檢查這兩個點是否存在if (pointSet.contains(p3) && pointSet.contains(p4)) {addSquare(squares, p1, p2, p3, p4);}// 情況2：另一個方向Point p5 = new Point(p2.x + dy, p2.y - dx);Point p6 = new Point(p1.x + dy, p1.y - dx);if (pointSet.contains(p5) && pointSet.contains(p6)) {addSquare(squares, p1, p2, p5, p6);}}}System.out.println(squares.size());}// 生成正方形的唯一鍵并存入集合private static void addSquare(Set<String> squares, Point... points) {List<Point> list = new ArrayList<>(Arrays.asList(points));// 按x和y排序，生成唯一鍵Collections.sort(list, (a, b) -> {if (a.x != b.x) return a.x - b.x;return a.y - b.y;});StringBuilder key = new StringBuilder();for (Point p : list) {key.append(p.x).append(',').append(p.y).append(';');}squares.add(key.toString());}
}

代碼詳細解析

1. Point類：封裝點的坐標，重寫equals和hashCode以便正確比較。
2. 輸入處理：讀取所有點并存入列表和集合，集合用于快速查找點是否存在。
3. 遍歷點對：雙重循環遍歷所有可能的點對，計算兩個可能的另外兩個點。
4. 向量旋轉：通過向量旋轉計算另外兩個點，檢查它們是否存在于集合中。
5. 唯一鍵生成：將四個點排序后生成字符串作為唯一標識，避免重復統計。
6. 輸出結果：集合的大小即為不同正方形的數量。

示例測試

示例1輸入：

3  
1 3  
2 4  
3 1  

輸出：

0  

解析：三點無法構成正方形。

示例2輸入：

4  
0 0  
1 2  
3 1  
2 -1  

輸出：

1  

解析：四個點構成一個正方形。

示例3輸入：

4  
0 0  
0 1  
1 1  
1 0  

輸出：

1  

解析：四個點構成一個正方形。

綜合分析

1. 時間復雜度：O(N2)，遍歷所有點對的時間復雜度為O(N2)，每次處理兩個可能的正方形。
2. 空間復雜度：O(N)，存儲點和集合的空間。
3. 優勢：通過向量旋轉快速確定可能的點，利用集合去重確保統計正確。
4. 適用場景：適用于坐標點數量適中的情況，高效且準確。

---

python

問題分析

給定 N 個二維坐標點，計算這些點能構成多少個不同的正方形。正方形的判定條件是四個點滿足特定幾何條件：所有邊長相等且相鄰邊垂直。需注意點互不相同且坐標范圍有限。

---

解題思路

1. 輸入處理：讀取所有點，存儲到列表和集合中，集合用于快速查找點是否存在。
2. 遍歷點對：對每兩個點，計算可能構成正方形的另外兩個點。
3. 向量旋轉：通過向量旋轉確定可能的另外兩個點位置，檢查是否存在。
4. 去重處理：將四個點排序后生成唯一標識，避免重復計數。

---

代碼實現

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
point_set = set(points)
squares