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.

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 

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).
  3. Input points have no order.

 

Approach #1: Math. [Java]

class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        long[] lengths = {length(p1, p2), length(p1, p3), length(p1, p4), 
                          length(p2, p3), length(p2, p4), length(p3, p4)};
        
        long maxLen = 0, count = 0, noMaxLen = 0;

        for (long len : lengths) 
            if (len > maxLen) maxLen = len;
        
        for (long len : lengths) {
            if (len == maxLen) count++;
            else noMaxLen = len; 
        }

        if (count != 2) return false;
        
        for (long len : lengths)
            if (len != maxLen && len != noMaxLen) return false;
        
        return true;
    }
    
    public long length(int[] p1, int[] p2) {
        return (long)Math.pow(p1[0] - p2[0], 2) + (long)Math.pow(p1[1] - p2[1], 2);
    }
}

　　

Analysis:

Just find the square of lengths, and validate that:

There are only two equal longest lengths.

The non longest lengths are all equal.

 

Reference:

https://leetcode.com/problems/valid-square/discuss/103435/Simple-Java-Solution-Square-distances

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄