Given the coordinates of four points in 2D space, return whether the four points could construct a square.
The coordinate (x,y) of a point is represented by an integer array with two integers.
Example:
Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True
Note:
All the input integers are in the range [-10000, 10000].
A valid square has four equal sides with positive length and four equal angles (90-degree angles).
Input points have no order.
Solution：
思路：
判断四个角是否是直角，但即便四个角都是直角，也不能说明一定就是正方形，还有可能是矩形。还得判断各边是否相等。
其实可以仅通过边的关系的来判断是否是正方形，根据初中几何的知识我们知道正方形的四条边相等，两条对角线相等，满足这两个条件的四边形一定是正方形。
我们只需要对四个点，两两之间算距离，如果计算出某两个点之间距离为0，说明两点重合了，直接返回false，如果不为0，那么我们就建立距离和其出现次数之间的映射，最后如果我们只得到了两个不同的距离长度，那么就说明是正方形了.
Time Complexity: O() Space Complexity: O()
Solution Code：
class Solution {
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
long[] lengths = {dist(p1, p2), dist(p2, p3), dist(p3, p4),
dist(p4, p1), dist(p1, p3), dist(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 dist(int[] p1, int[] p2) {
return (long)Math.pow(p1[0] - p2[0], 2) + (long)Math.pow(p1[1] - p2[1], 2);
}
}
