A general solution to find combination of squares in n points in O(n^2) time


  • 1

    The solution uses diag as the unique symbol to represent a square. First iterate through all possible edges and save in HashMap. In the second round, check each edge to see if the corresponding diag exists in Hash as well. If yes, add it to count.

    class Solution {
        public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
            if (p1 == null || p2 == null || p3 == null || p4 == null) return false;
            Map<String, Integer> map = new HashMap<>();
            List<int[]> list = new ArrayList<>();
            list.add(p1);
            list.add(p2);
            list.add(p3);
            list.add(p4);
            int count = 0;
            for (int i = 0; i < list.size() - 1; i++) {
                for (int j = i + 1; j < list.size(); j++) {
                    if (!check(list.get(i), list.get(j))) continue;
                    String str = genStr(list.get(i), list.get(j));
                    map.put(str, 1 + map.getOrDefault(str, 0));
                }
            }
            for (int i = 0; i < list.size() - 1; i++) {
                for (int j = i + 1; j < list.size(); j++) {
                    if (!check(list.get(i), list.get(j))) continue;
                    String diag = createDiag(list.get(i), list.get(j));
                    if (diag.length() == 0) continue;
                    count += map.getOrDefault(diag, 0);
                }
            }
            count >>= 1;
            return count > 0;
        }
        
        private boolean check(int[] p1, int[] p2) {
            if (p1[0] == p2[0] && p1[1] == p2[1]) return false;
            return true;
        }
        
        private String genStr(int[] p1, int[] p2) {
            if (p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1])) {
                return String.format("%d,%d;%d,%d", p1[0], p1[1], p2[0], p2[1]);
            } else {
                return String.format("%d,%d;%d,%d", p2[0], p2[1], p1[0], p1[1]);
            }
            
        }
        
        private String createDiag(int[] a, int[] c) {
            int midX = a[0] + c[0];
            int midY = a[1] + c[1];
    
            int Ax = 2*a[0] - midX;
            int Ay = 2*a[1] - midY;
            int bX = midX - Ay;
            int bY = midY + Ax;
    
            int cX = 2*c[0] - midX;
            int cY = 2*c[1] - midY;
            int dX = midX - cY;
            int dY = midY + cX;
            if ((bX & 1) == 0 && (bY & 1) == 0 && (dX & 1) == 0 && (dY & 1) == 0) {
                if (bX < dX || (bX == dX && bY < dY)) {
                    return String.format("%d,%d;%d,%d", bX/2, bY/2, dX/2, dY/2);
                } else {
                    return String.format("%d,%d;%d,%d", dX/2, dY/2, bX/2, bY/2);
                }
            } else {
                return "";
            }
        }
    }
    

  • 0
    S
    This post is deleted!

Log in to reply
 

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