# 华为机试【18、构成的正方形数量】

18、标题:构成的正方形数量
【构成正方形数量】输入N个互不相同的二维整数坐标，求这N个坐标可以构成的正方形数量。(内积为零的的两个向量垂直)

3
1 3
2 4
3 1

0

``````def square(s):
from itertools import combinations, permutations
def is_square(s):
arrs = permutations(s, 4)  # 因为不知道四个坐标的顺序，所以只好排列一下穷举所有可能的顺序，四个坐标排列，共有A(4, 4) = 24种情况
for arr in arrs:
ac = (arr[2][0] - arr[0][0], arr[2][1] - arr[0][1])
bd = (arr[3][0] - arr[1][0], arr[3][1] - arr[1][1])
ab = (arr[1][0] - arr[0][0], arr[1][1] - arr[0][1])
bc = (arr[2][0] - arr[1][0], arr[2][1] - arr[1][1])
dc = (arr[2][0] - arr[3][0], arr[2][1] - arr[3][1])
ad = (arr[3][0] - arr[0][0], arr[3][1] - arr[0][1])
if ac[0] * bd[0] + ac[1] * bd[1] == 0 and ab[0] * bc[0] + ab[1] * bc[1] == 0 and \
bc[0] * dc[0] + bc[1] * dc[1] == 0 and dc[0] * ad[0] + dc[1] * ad[1] == 0 and \
return True

if len(s) < 4:
return 0
num = 0
for arr in combinations(s, 4):  # 排列组合：C(len(s), 4)
arr = list(arr)
if is_square(arr):
num += 1
return num

# 下列9个点，可以组成6个正方形
#   * * *
#   * * *
#   * * *
print(square([(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]))
``````

1

OPPO

Java版本 https://blog.csdn.net/qq_34465338/article/details/124494644

3 6 评论