有效的正方形

难度: Medium

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

点的坐标 p_i 表示为 [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
-10⁴ <= x_i, y_i <= 10⁴

Submission

运行时间: 25 ms

内存: 16.0 MB

def checkLength(v1: Tuple[int, int], v2: Tuple[int, int]) -> bool:
    return v1[0] * v1[0] + v1[1] * v1[1] == v2[0] * v2[0] + v2[1] * v2[1]

def checkMidPoint(p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
    return p1[0] + p2[0] == p3[0] + p4[0] and p1[1] + p2[1] == p3[1] + p4[1]

def calCos(v1: Tuple[int, int], v2: Tuple[int, int]) -> int:
    return v1[0] * v2[0] + v1[1] * v2[1]

def help(p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
    v1 = (p1[0] - p2[0], p1[1] - p2[1])
    v2 = (p3[0] - p4[0], p3[1] - p4[1])
    return checkMidPoint(p1, p2, p3, p4) and checkLength(v1, v2) and calCos(v1, v2) == 0

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        if p1 == p2:
            return False
        if help(p1, p2, p3, p4):
            return True
        if p1 == p3:
            return False
        if help(p1, p3, p2, p4):
            return True
        if p1 == p4:
            return False
        if help(p1, p4, p2, p3):
            return True
        return False

# 抄官解。暴力枚举

Explain

这个题解的思路是通过检查两对对角线是否等长且垂直来判断四个点是否能构成一个正方形。首先定义了一些辅助函数：checkLength用于检查两个向量的长度是否相等，checkMidPoint用于检查两对点的中点是否相同，calCos用于计算两个向量的点积。然后定义了一个主要的辅助函数help，它接受四个点作为参数，计算两对对角线的向量，然后使用前面定义的辅助函数检查这两对对角线是否满足正方形的条件（等长且垂直）。最后，在Solution类中的validSquare方法中，首先检查任意两个点是否相同（如果相同，则它们不能构成正方形）。然后，它尝试将四个点分成不同的两对，使用help函数检查它们是否能构成正方形。如果其中任何一对满足条件，就返回True，否则返回False。

时间复杂度: O(1)

空间复杂度: O(1)

def checkLength(v1: Tuple[int, int], v2: Tuple[int, int]) -> bool:
    return v1[0] * v1[0] + v1[1] * v1[1] == v2[0] * v2[0] + v2[1] * v2[1]

def checkMidPoint(p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
    return p1[0] + p2[0] == p3[0] + p4[0] and p1[1] + p2[1] == p3[1] + p4[1]

def calCos(v1: Tuple[int, int], v2: Tuple[int, int]) -> int:
    return v1[0] * v2[0] + v1[1] * v2[1]

def help(p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
    v1 = (p1[0] - p2[0], p1[1] - p2[1])
    v2 = (p3[0] - p4[0], p3[1] - p4[1])
    return checkMidPoint(p1, p2, p3, p4) and checkLength(v1, v2) and calCos(v1, v2) == 0

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        if p1 == p2:
            return False
        if help(p1, p2, p3, p4):
            return True
        if p1 == p3:
            return False
        if help(p1, p3, p2, p4):
            return True
        if p1 == p4:
            return False
        if help(p1, p4, p2, p3):
            return True
        return False

Explore

题解中采用的是逐一比较的方法。具体地，它在调用`help`函数之前，会先检查`p1`是否与`p2`、`p3`或`p4`相同，以此类推。这种方法虽然直接，但在效率上并不是最优的。一个更高效的方法可能是使用哈希集合来存储所有点，然后检查集合的大小是否等于4（即没有重复的点），这样可以在常数时间内完成所有点对的比较。

向量的点积（或称为内积）定义为两个向量的对应坐标相乘后的总和。数学上，两个向量的点积等于它们的模长乘积与它们夹角的余弦值的乘积。当两个向量垂直时，它们之间的夹角为90度，余弦90度的值为0。因此，如果两个向量的点积为0，这意味着它们之间的夹角是90度，从而可以确认这两个向量是垂直的。

在平面几何中，正方形的两条对角线不仅等长且相互垂直，而且它们会在正方形的中心相交。这意味着两条对角线的中点必须相同，即是正方形的中心。因此，通过验证两对对角线的中点是否相同，可以帮助确认这四个点构成的四边形是否具有正方形的这一重要属性。

题解中尝试了三种不同的点对组合来形成两对对角线，分别是：(p1, p2)与(p3, p4)，(p1, p3)与(p2, p4)，(p1, p4)与(p2, p3)。这种方式是基于将四个点进行全排列后，选择可能的对角线组合。由于是要检查所有可能形成的对角线组合，因此选择的点对方式并不会影响最终结果。只要有任何一种组合满足正方形的条件，函数就会返回`True`。