Vector algebra based solution


  • 0

    We can fix one of the points say a and get all the four vectors that form the square. There are 6 ways to form these vectors given the starting point.

    Now, given two vectors AB and BC, we need to check if |AB|=|BC| and AB.BC = 0. Since cos 90 is 0, the dot products will be zero if they are at right angles. We need to repeat this for all 4 vectors of the square and all 6 squares until one of the combinations is true.

    I could have generated the 6 combinations as an improvement on the current code.

    public class Solution {
        public bool ValidSquare(int[] a, int[] b, int[] c, int[] d) {
            bool valid = IsValidSquare(a, b, c, d) || 
            IsValidSquare(a, b, d, c) ||
            IsValidSquare(a, c, b, d) ||
            IsValidSquare(a, c, d, b) || 
            IsValidSquare(a, d, b, c) ||
            IsValidSquare(a, d, c, b);
            return valid;
            
        }
        
        public bool IsValidSquare(int[] a, int[] b, int[] c, int[] d)
        {
            // Now consider the points in order.
            int[] AB = new int[] {b[0]-a[0], b[1]-a[1]};
            int[] BC = new int[] {c[0]-b[0], c[1]-b[1]};
            int[] CD = new int[] {d[0]-c[0], d[1]-c[1]};
            int[] DA = new int[] {a[0]-d[0], a[1]-d[1]};
            
            int m1 = GetSqMagnitude(AB);
            int m2 = GetSqMagnitude(BC);
            int m3 = GetSqMagnitude(CD);
            int m4 = GetSqMagnitude(DA);
            // If one of the magnitudes is zero, that means both points on one of the vectors are the same.
            if (m1 == 0 || m2 == 0 || m3 == 0 || m4 == 0)
            {
                return false;
            }
            
            if (m1 == m2 && m2 == m3 && m3 == m4 && m4 == m1)
            {
                if (IsRightAngle(AB, BC) && IsRightAngle(BC, CD) && IsRightAngle(CD, DA))
                {
                    return true;
                }
            }
            
            return false;
        }
        
        private int GetSqMagnitude(int[] v)
        {
            return v[0]*v[0] + v[1]*v[1];
        }
        
        private bool IsRightAngle(int[] v1, int[] v2)
        {
            int dot = (v1[0] * v2[0] + v1[1] * v2[1]);
            return (dot == 0);
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.