门户类网站图片,青岛免费模板建站,263企业邮箱app下载官网,网络热词2023文章目录 1.问题描述2.难度等级3.热门指数4.解题思路边长验证法等腰直角三角形验证法正方形定义 参考文献 1.问题描述
给定 2D 空间中四个点的坐标 p1, p2, p3 和 p4#xff0c;如果这四个点构成一个正方形#xff0c;则返回 true 。
点的坐标 pi 表示为 [xi, yi] 。 输入没… 文章目录 1.问题描述2.难度等级3.热门指数4.解题思路边长验证法等腰直角三角形验证法正方形定义 参考文献 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 intfor k : range set {if square1 0 {square1 kcontinue}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 直接返回 falseif 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
