593. Valid Square
Đề Bài
Given the coordinates of four points in 2D space p1, p2, p3 and p4, return true if the four points construct a square.
The coordinate of a point pi is represented as [xi, yi]. The input is not given in any order.
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Example 1:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1] Output: true
Example 2:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,12] Output: false
Example 3:
Input: p1 = [1,0], p2 = [-1,0], p3 = [0,1], p4 = [0,-1] Output: true
Constraints:
p1.length == p2.length == p3.length == p4.length == 2-104 <= xi, yi <= 104
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0593-valid-square.cpp
class Solution {
public:
int diff(vector<int> &p1, vector<int> &p2) {
int x1 = p1[0], y1 = p1[1];
int x2 = p2[0], y2 = p2[1];
return (x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2);
}
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
vector<vector<int>> p;
p.push_back(p1);
p.push_back(p2);
p.push_back(p3);
p.push_back(p4);
unordered_set<int> us;
const int n = (int)p.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int len = diff(p[i], p[j]);
if (len == 0) {
return false;
}
us.insert(len);
}
}
return us.size() == 2;
}
};