0593：有效的正方形（★）

力扣第 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

分析

• 最简单的是从边入手
• 正方形的四个点构成六条边，其中四边相等，两对角线相等，且对角线/边长=$\sqrt 2$
• 可以证明，符合条件的也必然是正方形

解答

1
2
3
4
5
6
7

class Solution:
    def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
        def cal(a,b):
            return (a[0]-b[0])**2+(a[1]-b[1])**2
        ct = Counter(cal(a,b) for a,b in combinations([p1,p2,p3,p4],2))
        x,y = min(ct),max(ct)
        return y==x*2 and ct[x]==4 and ct[y]==2

41 ms