Straightforward Java solution: check 3 points each time


  • 0
    Y

    A square has this property: if grab any 3 points to make a triangle, it is Isosceles right triangle.
    ![http://mathworld.wolfram.com/images/eps-gif/IsoscelesRightTriangle_1000.gif](image url)

    We can use this property to solve this problem.

    For example, there 4 points [0,1], [1,2], [2,1], [1,0]
    pick 3 of them: [0,1], [1,2], [2,1],
    so we can build 3 vectors (edges): [1,1], [1,-1], [2,0]
    these vector can build a Isosceles right triangle because vector [1,1] and [1,-1] has same length, and they are vertical (because inner product is 0).

        public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
            return check(p1,p2,p3) && check(p1,p2,p4) && check(p1,p3,p4) && check(p2,p3,p4);
        }
        
        public boolean check(int[] p1, int[] p2, int[] p3) { 
            int[] vec1 = {p1[0]-p2[0], p1[1]-p2[1]};
            int[] vec2 = {p1[0]-p3[0], p1[1]-p3[1]};
            int[] vec3 = {p2[0]-p3[0], p2[1]-p3[1]};
            
            return L(vec1,vec2) || L(vec2,vec3) || L(vec1, vec3);
        }
        
        public boolean L(int[] p, int[] q) {
        // check whether two vector are non-zero, has equal length and can build a vertical corner
            return p[0]*p[0]+p[1]*p[1]!= 0 && q[0]*q[0]+q[1]*q[1] != 0 &&(p[0]*p[0]+p[1]*p[1] == q[0]*q[0]+q[1]*q[1]) && (p[0]*q[0]+p[1]*q[1] == 0);
        }
    

Log in to reply
 

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