There are a lot of approaches to this question really. Below are a few of them.
Approach 1
Consider distance between all the points. If it forms a sqaure, there should only be two unique distances: one for the sides and one for the diagonals. Further, there should be four equal distances belonging to the sides and two equal distances belonging to the diagonals (this distance should be greater than that of sides).
// JAVA solution
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
long[] lengths = {length(p1, p2), length(p2, p3), length(p3, p4),
length(p4, p1), length(p1, p3),length(p2, p4)}; // all 6 sides
long max = 0, nonMax = 0;
for(long len : lengths) {
max = Math.max(max, len);
}
int count = 0;
for(int i = 0; i < lengths.length; i++) {
if(lengths[i] == max) count++;
else nonMax = lengths[i]; // non diagonal side.
}
if(count != 2) return false; // diagonals lengths have to be same.
for(long len : lengths) {
if(len != max && len != nonMax) return false; // sides have to be same length
}
return true;
}
private long length(int[] p1, int[] p2) {
return (long)Math.pow(p1[0]-p2[0],2) + (long)Math.pow(p1[1]-p2[1], 2);
}
This is another implementation (by votrubac) with the same idea:
If we calculate all distances between 4 points, 4 smaller distances should be equal (sides), and 2 larger distances should be equal too (diagonals). As an optimization, we can compare squares of the distances, so we do not have to deal with the square root and precision loss. Therefore, our set will only contain 2 unique distances in case of square (beware of the zero distance though).
int d(vector<int>& p1, vector<int>& p2) {
return (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]);
}
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
unordered_set<int> s({ d(p1, p2), d(p1, p3), d(p1, p4), d(p2, p3), d(p2, p4), d(p3, p4) });
return !s.count(0) && s.size() == 2;
}
Approach 2
This approach shows how I solved the problem initially. Though this is a longer approach, it popped my mind first. Consider each unique pair of points to be two ends of a diagonal. Let’s say we consider p1 and p2 to be two ends of a diagonal. This way, p3 and p4 would be the two ends of the other diagonal. To make a square, these conditions should be valid:
- Length of side (p1,p3) = length of side (p2,p3)
- Side (p1,p3) and Side (p2,p3) form a 90deg angle
- Length of side (p1,p4) = length of side (p2,p4)
- Side (p1,p4) and Side (p2,p4) form a 90deg angle
Finding lengths is easy. To check for a right angle, let’s use the dot product of the two sides!
The dot product of two vectors is
a . b = |a|x|b|xcos(t)where t is the angle between the vectors.
If t=90deg, clearly the dost product is 0. Getting the vectors is easy. If we consider the sides (p1,p3) and (p2,p3) the the vectors will be:
a = (x3-x1, y3-y1)
b = (x3-x2, y3-y2)
a . b = (x3-x1)*(x3-x2) + (y3-y1)*(y3-y2) = 0
class Solution {
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
// possible unique diagonals: {p1,p2}, {p1, p3}, {p1, p4}
bool isPossible = false;
isPossible = isPossible || (isEqualDist(p1, p2, p3) && isEqualDist(p1,p2,p4) && isRightAngle(p1,p2,p3) && isRightAngle(p1,p2,p4));
isPossible = isPossible || (isEqualDist(p1, p3, p2) && isEqualDist(p1,p3,p4) && isRightAngle(p1,p3,p2) && isRightAngle(p1,p3,p4));
isPossible = isPossible || (isEqualDist(p1, p4, p2) && isEqualDist(p1,p4,p3) && isRightAngle(p1,p4,p2) && isRightAngle(p1,p4,p3));
return isPossible;
}
bool isEqualDist (vector<int> diag1, vector<int> diag2, vector<int> p) {
int dist1 = (diag1[0]-p[0])*(diag1[0]-p[0])+(diag1[1]-p[1])*(diag1[1]-p[1]);
return dist1>0 && dist1 == (diag2[0]-p[0])*(diag2[0]-p[0])+(diag2[1]-p[1])*(diag2[1]-p[1]);
}
bool isRightAngle (vector<int> diag1, vector<int> diag2, vector<int> p) {
return (diag1[0]-p[0])*(diag2[0]-p[0])+(diag1[1]-p[1])*(diag2[1]-p[1]) == 0;
}
};