package leetcode;

/**
 * https://leetcode.com/problems/number-of-boomerangs/
 */
public class Problem447 {
    public int numberOfBoomerangs(int[][] points) {
        int result = 0;
        for (int i = 0; i < points.length; i++) {
            for (int j = 0; j < points.length; j++) {
                if (i == j) {
                    continue;
                }
                int distance1 = getDistance(points, i, j);
                for (int k = 0; k < points.length; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    int distance2 = getDistance(points, i, k);
                    if (distance1 == distance2) {
                        result++;
                    }
                }
            }
        }
        return result;
    }

    private static int getDistance(int[][] points, int i, int j) {
        int a = points[i][0] - points[j][0];
        int b = points[i][1] - points[j][1];
        return (a * a) + (b * b);
    }

    public static void main(String[] args) {
        Problem447 prob = new Problem447();
        System.out.println(prob.numberOfBoomerangs(new int[][]{{0, 0}, {1, 0}, {2, 0}})); // 2
        System.out.println(prob.numberOfBoomerangs(new int[][]{{1, 4}, {0, 8}, {2, 8}, {4, 5}})); // 2
        System.out.println(prob.numberOfBoomerangs(new int[][]{{0, 0}, {1, 0}, {-1, 0}, {0, 1}, {0, -1}})); // 20
    }
}

@@ -12,16 +12,65 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -214,22 +214,61 @@
     
-int result = 0
+Map%3CString, Integer%3E distanceCounts = new HashMap%3C%3E()
 ;%0A  
@@ -467,23 +467,30 @@
     
-int distance1 =
+String key = i + %22%7C%22 +
  get
@@ -533,336 +533,570 @@
     
-for (int k = 0; k %3C points.length; k++) %7B%0A                    if (k == i %7C%7C k == j) %7B%0A                        continue;%0A                    %7D%0A                    int distance2 = getDistance(points, i, k);%0A                    if (distance1 == distance2) %7B%0A                        result++;%0A                    %7D%0A                %7D
+if (!distanceCounts.containsKey(key)) %7B%0A                    distanceCounts.put(key, 1);%0A                %7D else %7B%0A                    distanceCounts.put(key, distanceCounts.get(key) + 1);%0A                %7D%0A            %7D%0A        %7D%0A        int result = 0;%0A        for (int i = 0; i %3C points.length; i++) %7B%0A            for (int j = 0; j %3C points.length; j++) %7B%0A                if (i == j) %7B%0A                    continue;%0A                %7D%0A                int distance = getDistance(points, i, j);%0A                result += distanceCounts.get(i + %22%7C%22 + distance) - 1;
 %0A   

Update problem 447