593. Valid Square
1. Description
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 [x$_i$, y$_i$]. 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).
2. Example
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
3. Constraints
- p1.length == p2.length == p3.length == p4.length == 2
- -10$^4$ <= xi, yi <= 10$^4$
4. Solutions
Math
Time complexity: O(1)
Space complexity: O(1)
class Solution {
public:
bool validSquare(
const vector<int> &p1,
const vector<int> &p2,
const vector<int> &p3,
const vector<int> &p4) {
vector<int> distances{
distance(p1, p2),
distance(p1, p3),
distance(p1, p4),
distance(p2, p3),
distance(p2, p4),
distance(p3, p4)};
sort(distances.begin(), distances.end());
return distances[0] != 0 && distances[0] == distances[1] && distances[0] == distances[2] &&
distances[0] == distances[3] && distances[4] == distances[5] &&
distances[4] > distances[0];
}
private:
int distance(const vector<int> &p1, const vector<int> &p2) {
int dx = p1[0] - p2[0];
int dy = p1[1] - p2[1];
return dx * dx + dy * dy;
}
};