给定 2D 空间中四个点的坐标 p1, p2, p3 和 p4,如果这四个点构成一个正方形,则返回 true 。
点的坐标 pi 表示为 [xi, yi] 。 输入没有任何顺序 。
一个「有效的正方形」有四条等边和四个等角(90度角)。
Medium。
★★★★☆
出题公司:腾讯。
正方形四个点构成的六条线(四边+两对角线)有如下特征:
根据上面的特点,我们可以计算出任意两点之间的距离来判断是否是正方形。
注意:判断过程中,不用计算出两点实际距离,只需要算出距离的平方即可。不然会存在浮点数,可能会有精度丢失,导致结果出错。
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
}