力扣题目链接:https://leetcode.cn/problems/valid-square/
给定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
如果四个点能组成一个正方形,那么这 4 4 4个点必须满足以下 3 3 3个条件:
第 1 1 1条比较容易理解,如果满足第 2 2 2条,那么四边形就是菱形
只要菱形中存在一个直角(第 3 3 3条),那么这个菱形就是矩形
有没有重合的点:
把四个点添加到一个数组里,然后用 i i i和 j j j遍历数组,一一判断是否有重合的点。
四条边等长:
注意,我们不知道哪两个点是一条边上的点,哪两个点是对角上的点。
但是只有 4 4 4个点,我们把 4 4 4个点的相对顺序,全部模拟一遍即可。
也就是说求一遍 4 4 4个点的全排列。
存在直角:
相比起来,这个就很容易判断了。
直接使用勾股定理即可。
如果想要debug某个点,可以重载运算符
ostream& operator<< (ostream& out, vector<int>& v) {
out << '[';
for (int i = 0; i < v.size(); i++) {
if (i)
out << ", ";
out << v[i];
}
out << ']';
return out;
}
这样,我们直接cout
某个点即可:
cout << "Ok: [" << v[0] << ", " << v[1] << ", " << v[2] << ", " << v[3] << endl;
class Solution {
private:
/* 计算两个点之间的距离 */
inline int distance2(vector<int>& a, vector<int>& b) {
return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
}
bool ifOkThisOrder(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
int d12 = distance2(p1, p2);
int d23 = distance2(p2, p3);
int d34 = distance2(p3, p4);
int d41 = distance2(p4, p1);
// 四条边等长
if (d12 != d23 || d23 != d34 || d34 != d41)
return false;
// 有直角
return d12 + d23 == distance2(p1, p3);
}
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
vector<int> v[4] = {p1, p2, p3, p4};
// 点不重合
for (int i = 0; i < 4; i++) {
for (int j = i + 1; j < 4; j++) {
if (v[i] == v[j])
return false;
}
}
vector<int> order = {0, 1, 2, 3};
do {
if (ifOkThisOrder(v[order[0]], v[order[1]], v[order[2]], v[order[3]])) {
// cout << "Ok: [" << v[order[0]] << ", " << v[order[1]] << ", " << v[order[2]] << ", " << v[order[3]] << endl;
return true;
}
} while (next_permutation(order.begin(), order.end()));
return false;
}
};
同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/126053093