有效的正方形（LeetCode 593）

1.问题描述

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

点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。

一个「有效的正方形」有四条等边和四个等角（90度角）。

2.难度等级

Medium。

3.热门指数

★★★★☆

出题公司：腾讯。

4.解题思路

边长验证法

正方形四个点构成的六条线（四边+两对角线）有如下特征：

• 四边长度相等
• 边长平方和等于对角线平方

根据上面的特点，我们可以计算出任意两点之间的距离来判断是否是正方形。

注意：判断过程中，不用计算出两点实际距离，只需要算出距离的平方即可。不然会存在浮点数，可能会有精度丢失，导致结果出错。

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
    l1 := lenSquare(p1, p2)
    l2 := lenSquare(p1, p3)
    l3 := lenSquare(p1, p4)
    l4 := lenSquare(p2, p3)
    l5 := lenSquare(p2, p4)
    l6 := lenSquare(p3, p4)

    set := map[int]struct{}{}
    set[l1] = struct{}{}
    set[l2] = struct{}{}
    set[l3] = struct{}{}
    set[l4] = struct{}{}
    set[l5] = struct{}{}
    set[l6] = struct{}{}
    
    if len(set) != 2 {
        return false
    }
    var square1, square2 int
    for k := range set {
        if square1 == 0 {
            square1 = k
            continue
        }
        square2 = k
    }
    if square1 < square2 {
        return square1*2 == square2
    }
    return square2*2 == square1
}

func lenSquare(p1, p2 []int) int {
    x := p1[0] - p2[0]
    y := p1[1] - p2[1]
    return x*x + y*y
}

等腰直角三角形验证法

正方形可以将其拆分成四个等腰直角三角形，所以枚举由三个点构成的三角形是否时等腰直角三角形即可。

如果三角形两个边相等，则为直角边。如果直角边的平方和等于另一条边的平方，那么可断定为等腰直角三角形。

func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
    return isosceles(p1, p2, p3) && isosceles(p1, p2, p4) && isosceles(p1, p3, p4) && isosceles(p2, p3, p4)
}

// isosceles 是否等腰直角三角形
func isosceles(p1, p2, p3 []int) bool {
    l1 := lenSquare(p1, p2)
    l2 := lenSquare(p1, p3)
    l3 := lenSquare(p2, p3)

    // 边长为 0 直接返回 false
    if l1 == 0 || l2 == 0 || l3 == 0 {
        return false
    }

    if l1 > l2 {
        return l1 == l2 + l3 && l2 == l3
    }
    if l2 > l3 {
        return l2 == l1 + l3 && l1 == l3
    }
    if l3 > l1 {
        return l3 == l1 + l2 && l1 == l2
    }
    return false
}

func lenSquare(p1, p2 []int) int {
    x := p1[0] - p2[0]
    y := p1[1] - p2[1]
    return x*x + y*y
}

正方形判定定理

正方形是特殊的平行四边形。即有一组邻边相等，并且有一个角是直角的平行四边形称为正方形。

• 如果两条斜边的中点相同：则说明以该两条斜边组成的四边形为「平行四边形」。
• 在满足「条件一」的基础上，如果两条斜边的长度相同：则说明以该两条斜边组成的四边形为「矩形」。
• 在满足「条件二」的基础上，如果两条斜边的相互垂直：则说明以该两条斜边组成的四边形为「正方形」。

func checkLength(v1, v2 []int) bool {
    return v1[0]*v1[0]+v1[1]*v1[1] == v2[0]*v2[0]+v2[1]*v2[1]
}

func checkMidPoint(p1, p2, p3, p4 []int) bool {
    return p1[0]+p2[0] == p3[0]+p4[0] && p1[1]+p2[1] == p3[1]+p4[1]
}

func calCos(v1, v2 []int) int {
    return v1[0]*v2[0] + v1[1]*v2[1]
}

func help(p1, p2, p3, p4 []int) bool {
    v1 := []int{p1[0] - p2[0], p1[1] - p2[1]}
    v2 := []int{p3[0] - p4[0], p3[1] - p4[1]}
    return checkMidPoint(p1, p2, p3, p4) && checkLength(v1, v2) && calCos(v1, v2) == 0
}

func validSquare(p1, p2, p3, p4 []int) bool {
    // p1 和 p2 为同一个点
    if p1[0] == p2[0] && p1[1] == p2[1] {
        return false
    }
    // p1 与 p2 构成对角线
    if help(p1, p2, p3, p4) {
        return true
    }

	// p1 和 p3 为同一个点
    if p1[0] == p3[0] && p1[1] == p3[1] {
        return false
    }
    // p1 与 p3 构成对角线
    if help(p1, p3, p2, p4) {
        return true
    }

	// p1 和 p4 为同一个点
    if p1[0] == p4[0] && p1[1] == p4[1] {
        return false
    }
    // p1 与 p4 构成对角线
    if help(p1, p4, p2, p3) {
        return true
    }
    return false
}

参考文献

593. 有效的正方形 - LeetCode