class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
}
};
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原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2023-06-12 16:16:13
func validSquare(p1 []int, p2 []int, p3 []int, p4 []int) bool {
points, counter, distance := [][]int{p1, p2, p3, p4}, map[int]int{}, func(a []int, b []int) int {
return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1])
}
for i, n := 0, len(points); i < n - 1; i++ {
for j := i + 1; j < n; j++ {
counter[distance(points[i], points[j])] += 1
}
}
if len(counter) != 2 {
return false
}
x, y := int(1E9), 0
for k, _ := range counter {
if x == 1E9 {
x = k
} else {
y = k
}
}
if x > y {
x, y = y, x
}
return y == 2 * x && counter[x] == 4 && counter[y] == 2
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16 MB, 提交时间: 2023-06-12 16:15:45
class Solution:
def validSquare(self, p1: List[int], p2: List[int], p3: List[int], p4: List[int]) -> bool:
return items[0][1] == 4 and items[1][1] == 2 and items[1][0] == 2 * items[0][0] if \
(dist_cnts := Counter((b[0] - a[0]) ** 2 + (b[1] - a[1]) ** 2 for a, b in itertools.combinations([p1, p2, p3, p4], 2))) \
and len(items := sorted(dist_cnts.items())) == 2 else False
cpp 解法, 执行用时: 12 ms, 内存消耗: 26.2 MB, 提交时间: 2023-06-12 16:13:48
#define Cen2Ori(p) {p[0]*4-cenX, p[1]*4-cenY}
class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
// 中心点，缩放 4 倍，避免除法
int cenX = p1[0] + p2[0] + p3[0] + p4[0];
int cenY = p1[1] + p2[1] + p3[1] + p4[1];
// 将中心点移动到坐标原点
vector<array<int, 2>> pts = {Cen2Ori(p1), Cen2Ori(p2), Cen2Ori(p3), Cen2Ori(p4)};
// 将四个顶点存入哈希表
auto arrayHash = [fn = hash<long>{}] (const array<int, 2>& arr) -> size_t { // 哈希函数
return fn(*((long const*)arr.data()));
};
unordered_set<array<int, 2>, decltype(arrayHash)> pts_set(pts.begin(), pts.end(), 0, arrayHash);
if(pts_set.size() < 4) return false;
// 检查每个点旋转 90 度以后的点是否在哈希表中
for(auto &pt: pts){
if(!pts_set.count({-pt[1], pt[0]})) return false;
}
return true;
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-06-12 16:12:47
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 {
if p1[0] == p2[0] && p1[1] == p2[1] {
return false
}
if help(p1, p2, p3, p4) {
return true
}
if p1[0] == p3[0] && p1[1] == p3[1] {
return false
}
if help(p1, p3, p2, p4) {
return true
}
if p1[0] == p4[0] && p1[1] == p4[1] {
return false
}
if help(p1, p4, p2, p3) {
return true
}
return false
}
java 解法, 执行用时: 1 ms, 内存消耗: 39.4 MB, 提交时间: 2023-06-12 16:12:31
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
if (Arrays.equals(p1, p2)) {
return false;
}
if (help(p1, p2, p3, p4)) {
return true;
}
if (Arrays.equals(p1, p3)) {
return false;
}
if (help(p1, p3, p2, p4)) {
return true;
}
if (Arrays.equals(p1, p4)) {
return false;
}
if (help(p1, p4, p2, p3)) {
return true;
}
return false;
}
public boolean help(int[] p1, int[] p2, int[] p3, int[] p4) {
int[] v1 = {p1[0] - p2[0], p1[1] - p2[1]};
int[] v2 = {p3[0] - p4[0], p3[1] - p4[1]};
if (checkMidPoint(p1, p2, p3, p4) && checkLength(v1, v2) && calCos(v1, v2)) {
return true;
}
return false;
}
public boolean checkLength(int[] v1, int[] v2) {
return (v1[0] * v1[0] + v1[1] * v1[1]) == (v2[0] * v2[0] + v2[1] * v2[1]);
}
public boolean checkMidPoint(int[] p1, int[] p2, int[] p3, int[] p4) {
return (p1[0] + p2[0]) == (p3[0] + p4[0]) && (p1[1] + p2[1]) == (p3[1] + p4[1]);
}
public boolean calCos(int[] v1, int[] v2) {
return (v1[0] * v2[0] + v1[1] * v2[1]) == 0;
}
}
python3 解法, 执行用时: 40 ms, 内存消耗: 16.2 MB, 提交时间: 2023-06-12 16:12:08
# 数学解法
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