題目描述

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

輸入描述
第一行輸入為N，N代表坐標數量，N為正整數。N <= 100
之后的 K 行輸入為坐標x y以空格分隔，x，y為整數，-10<=x, y<=10

輸出描述
輸出可以構成的正方形數量。

用例
輸入

3
1 3
2 4
3 1

輸出

0

說明

（3個點不足以構成正方形）

輸入

4
0 0
1 2
3 1
2 -1

輸出

1

二維坐標構成正方形數量計算

核心解題思路

該題的關鍵在于利用幾何性質來高效判斷正方形的存在。已知兩個點((x_1,y_1))和((x_2,y_2))，根據正方形的幾何特征，可通過向量旋轉(90^{\circ})的方式計算出另外兩個可能的對角點坐標。

向量(\overrightarrow{AB}=(x_2 - x_1, y_2 - y_1))，將其旋轉(90^{{\circ})（順時針或逆時針），得到新向量。若原向量為((a,b))，順時針旋轉(90}{\circ})后為((b,-a))，逆時針旋轉(90^{\circ})后為((-b,a))。基于此，根據已知兩點計算出另外兩個可能的對角點坐標，然后檢查這兩個點是否都存在于給定的坐標列表中。若存在，則說明這四個點可以構成一個正方形。由于每個正方形在遍歷點對的過程中會被計算(4)次（不同的邊作為起始邊），所以最終結果需要除以(4)。

完整代碼實現

# 定義一個函數來判斷兩個點是否相等
def are_points_equal(p1, p2):return p1[0] == p2[0] and p1[1] == p2[1]# 定義一個函數來檢查一個點是否存在于點列表中
def point_exists(points, p):for point in points:if are_points_equal(point, p):return Truereturn False# 讀取坐標數量
n = int(input())
coordinates = []# 讀取坐標并存入列表
for _ in range(n):x, y = map(int, input().split())coordinates.append((x, y))square_count = 0# 遍歷所有點對，檢查是否能構成正方形
for i in range(n):x1, y1 = coordinates[i]for j in range(i + 1, n):x2, y2 = coordinates[j]# 計算兩個可能的對角點x3, y3 = x1 - (y1 - y2), y1 + (x1 - x2)x4, y4 = x2 - (y1 - y2), y2 + (x1 - x2)p3 = (x3, y3)p4 = (x4, y4)if point_exists(coordinates, p3) and point_exists(coordinates, p4):square_count += 1# 計算另外兩個可能的對角點x5, y5 = x1 + (y1 - y2), y1 - (x1 - x2)x6, y6 = x2 + (y1 - y2), y2 - (x1 - x2)p5 = (x5, y5)p6 = (x6, y6)if point_exists(coordinates, p5) and point_exists(coordinates, p6):square_count += 1# 每個正方形被計算了4次，因此結果需要除以4
print(square_count // 4)

算法原理解析

點相等判斷函數 are_points_equal

該函數通過比較兩個點坐標的(x)值和(y)值是否分別相等，來判斷兩個點是否為同一個點。若(p1)的(x)坐標等于(p2)的(x)坐標，且(p1)的(y)坐標等于(p2)的(y)坐標，則返回 True，否則返回 False。

點存在檢查函數 point_exists

遍歷給定的點列表 points，對于列表中的每一個點，調用 are_points_equal 函數檢查其是否與目標點 p 相等。若存在相等的點，則返回 True，表示目標點存在于列表中；遍歷結束仍未找到相等的點，則返回 False。

主邏輯

• 讀取坐標數量 n 和具體的坐標值并存入列表 coordinates。
• 兩層循環遍歷所有的點對 ((i, j))（(i < j)）：
  • 根據當前點對的坐標 ((x_1,y_1)) 和 ((x_2,y_2))，通過向量旋轉的幾何原理計算出兩組可能的對角點坐標（如 (x3,y3)、(x4,y4) 和 (x5,y5)、(x6,y6) ）。
  • 分別檢查每組對角點是否都存在于 coordinates 列表中。若存在，則 square_count 計數器加 (1)。
• 由于每個正方形在遍歷點對的過程中會被計算 (4) 次（不同的邊作為起始邊），所以最終結果 square_count 需要除以 (4) 得到實際的正方形數量。

示例解析

示例一（輸入 (3) 個點）

輸入：

3
1 3
2 4
3 1

在兩層循環中，由于只有 (3) 個點，當外層循環 i 取到 (2)（索引從 (0) 開始）時，內層循環 j 從 (i + 1 = 3) 開始，而總共有 (3) 個點，索引最大為 (2)，內層循環不會執行。因此，square_count 始終為 (0)，最終輸出 (0)，符合 (3) 個點無法構成正方形的條件。

示例二（輸入 (4) 個點能構成 (1) 個正方形）

輸入：

4
0 0
1 2
3 1
2 -1

假設我們取點對 ((0,0)) 和 ((1,2))：

• 計算第一組對角點：
  (x3 = 0 - (0 - 2) = 2)，(y3 = 0 + (0 - 1) = -1)，即 (p3 = (2,-1))
  (x4 = 1 - (0 - 2) = 3)，(y4 = 2 + (0 - 1) = 1)，即 (p4 = (3,1))
  檢查發現 (p3) 和 (p4) 都存在于坐標列表中，square_count 加 (1)。
• 計算第二組對角點時（可能不符合條件，此處不詳細展開）。
  由于存在這樣一組符合條件的對角點，且經過其他點對計算（可能重復計算同一個正方形的不同邊），最終 square_count 會累加到 (4)（因為每個正方形被計算 (4) 次），除以 (4) 后輸出 (1)。

總結

此代碼通過巧妙利用幾何中向量旋轉的性質，避免了復雜的四重循環判斷所有四個點組合的方式，大大提高了計算效率。對于初學者來說，理解向量旋轉與坐標計算的關系是關鍵。通過 are_points_equal 和 point_exists 函數實現了點的基本操作判斷，主邏輯部分通過遍歷點對并結合幾何計算來統計正方形數量。這種方法不僅在代碼實現上相對簡潔，而且在算法效率上也有較好的表現，適用于給定規模（(N <= 100)）的坐標輸入情況。通過對示例的分析，能更清晰地看到代碼如何根據輸入數據進行計算并得出正確結果，有助于深入理解整個算法流程。