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

18、标题:构成的正方形数量
【构成正方形数量】输入N个互不相同的二维整数坐标,求这N个坐标可以构成的正方形数量。(内积为零的的两个向量垂直)
输入描述:
第一行输入为N,N代表坐标数量,N为正整数。N<=100之后的K行输入为坐标xy以空格分隔,xy为整数,-10<=x,y<=10
输出描述:
输出可以构成的正方形数量。
示例1:输入
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])
            # 对角线垂直,临边均相互垂直的四边形为正方形,即:ac⊥bd、ab⊥bc、bc⊥dc、dc⊥ad、ad⊥ab
            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 \
                    ad[0] * ab[0] + ad[1] * ab[1] == 0:
                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)]))
全部评论
这样会超时,通过率只有30左右
1
送花
回复 分享
发布于 2022-06-25 18:33
感觉这道题完全就是在考察数学啊,又是排列又是组合,另外还有向量点积,太难了
点赞
送花
回复 分享
发布于 2022-04-01 12:15
OPPO
校招火热招聘中
官网直投
Java版本 https://blog.csdn.net/qq_34465338/article/details/124494644
点赞
送花
回复 分享
发布于 2022-05-15 20:26
如果只用两个点来决定一个正方形,然后再判断是否四个点都齐全,然后循环会不会更好点。
点赞
送花
回复 分享
发布于 2023-02-24 17:56 天津

相关推荐

3 6 评论
分享
牛客网
牛客企业服务