LeetCode 593 - Valid Square

https://leetcode.com/problems/valid-square
http://bookshadow.com/weblog/2017/05/21/leetcode-valid-square/

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:

1. All the input integers are in the range [-10000, 10000].
2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).

https://discuss.leetcode.com/topic/89995/simple-java-solution-square-distances

Just find the square of lengths, and validate that

1. There are only two equal longest lengths.
2. The non longest lengths are all equal.

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 lenghts 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);
}

https://discuss.leetcode.com/topic/89986/java-solution-calculate-distance-from-rest-of-the-points
Reference: http://www.geeksforgeeks.org/check-given-four-points-form-square/

    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        if (p1[0] == p2[0] && p1[1] == p2[1]
            || p1[0] == p3[0] && p1[1] == p3[1]
            || p1[0] == p4[0] && p1[1] == p4[1]) return false;
        
        int d2 = distSq(p1, p2);  // from p1 to p2
        int d3 = distSq(p1, p3);  // from p1 to p3
        int d4 = distSq(p1, p4);  // from p1 to p4
     
        // If lengths if (p1, p2) and (p1, p3) are same, then
        // following conditions must met to form a square.
        // 1) Square of length of (p1, p4) is same as twice
        //    the square of (p1, p2)
        // 2) p4 is at same distance from p2 and p3
        if (d2 == d3 && 2 * d2 == d4) {
            int d = distSq(p2, p4);
            return (d == distSq(p3, p4) && d == d2);
        }
     
        // The below two cases are similar to above case
        if (d3 == d4 && 2 * d3 == d2) {
            int d = distSq(p2, p3);
            return (d == distSq(p2, p4) && d == d3);
        }
        
        if (d2 == d4 && 2*d2 == d3) {
            int d = distSq(p2, p3);
            return (d == distSq(p3, p4) && d == d2);
        }
     
        return false;
    }
    
    int distSq(int[] p, int[] q) {
        return (p[0] - q[0])*(p[0] - q[0]) + (p[1] - q[1])*(p[1] - q[1]);
    }

记4个点中最左下方的点为lb

以lb为极点对其余点进行极坐标排序，记排序后的点为pts

判断pts[0] - pts[1]; pts[1] - pts[2]; pts[2] - pts[3]; pts[3] - pts[0]是否距离为0

判断pts[0] - pts[1]; pts[1] - pts[2]; pts[2] - pts[3]; pts[3] - pts[0]是否相等

判断pts[0] - pts[1]平方的二倍是否等于pts[0] - pts[2]