【LeetCode】593. 有效的正方形

题目

593. 有效的正方形

给定2D空间中四个点的坐标 p1, p2, p3 和 p4，如果这四个点构成一个正方形，则返回 true 。

点的坐标 pi 表示为 [xi, yi] 。输入 不是 按任何顺序给出的。

一个 有效的正方形 有四条等边和四个等角(90度角)。

示例 1:

输入: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
输出: True

示例 2:

输入：p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12]
输出：false

示例 3:

输入：p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1]
输出：true

提示:

• p1.length == p2.length == p3.length == p4.length == 2
• -104 <= xi, yi <= 104

思路

• 使用临边垂直的定理求取p1的两个临近点
• 取得p1的临近点和远点后，计算四条边的向量
• 使用：对边平行且相等，临边垂直且相等的定理结合向量向量运算进行判断
• 四个点重合的情况非正方形，单独判断

代码

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        v1 = (p2[0] - p1[0], p2[1]-p1[1])
        v2 = (p3[0] - p1[0], p3[1]-p1[1])
        v3 = (p4[0] - p1[0], p4[1]-p1[1])
        
        if v1[0]*v2[0]+v1[1]*v2[1] == 0:
            neighbor1,neighbor2,far = p2,p3,p4
        elif v1[0]*v3[0]+v1[1]*v3[1] == 0:
            neighbor1,neighbor2,far = p2,p4,p3
        elif v2[0]*v3[0]+v2[1]*v3[1] == 0:
            neighbor1,neighbor2,far = p3,p4,p2
        else:
            return False
        v1 = (neighbor1[0]-p1[0], neighbor1[1]-p1[1])
        v2 = (neighbor2[0]-p1[0], neighbor2[1]-p1[1])
        v3 = (far[0]-neighbor2[0], far[1]-neighbor2[1])
        v4 = (far[0]-neighbor1[0], far[1]-neighbor1[1])

        return (v1[0]*v3[1]-v1[1]*v3[0] == 0) and (v1[0]**2+v1[1]**2 == v3[0]**2+v3[1]**2) and (v1[0]*v2[0]+v1[1]*v2[1] == 0) and (v1[0]**2+v1[1]**2 == v2[0]**2+v2[1]**2) and p1!=p2!=p3!=p4

复杂度

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$