Maximum Number of Darts Inside of a Circular Dartboard

You have a very large square wall and a circular dartboard placed on the wall. You have been challenged to throw darts into the board blindfolded. Darts thrown at the wall are represented as an array of points on a 2D plane.

Return the maximum number of points that are within or lie on any circular dartboard of radius r.

Example 1:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
Output: 4
Explanation: Circle dartboard with center in (0,0) and radius = 2 contain all points.

Example 2:

Input: points = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
Output: 5
Explanation: Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).

Example 3:

Input: points = [[-2,0],[2,0],[0,2],[0,-2]], r = 1
Output: 1

Example 4:

Input: points = [[1,2],[3,5],[1,-1],[2,3],[4,1],[1,3]], r = 2
Output: 4

Constraints:

• 1 <= points.length <= 100

• points[i].length == 2

• -10^4 <= points[i][0], points[i][1] <= 10^4

• 1 <= r <= 5000

// http://mathforum.org/library/drmath/view/53027.html
class Solution {
    public int numPoints(int[][] points, int r) {
        int max = 0;
        // If we take every point as center
        for (int i = 0; i < points.length; i++) {
            int count = 0;
            for (int j = 0; j < points.length; j++) {
                if (Math.pow(points[j][0] - points[i][0], 2) + Math.pow(points[j][1] - points[i][1], 2) <= r * r)
                    count++;
            }
            max = Math.max(max, count);
        }
        // If the 2 points are are taken at circumference
        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < points.length; j++) {
                if (Math.pow(points[j][0] - points[i][0], 2) + Math.pow(points[j][1] - points[i][1], 2) > 4 * r * r)
                    continue;
                double q = Math.sqrt(Math.pow(points[j][0] - points[i][0], 2) + Math.pow(points[j][1] - points[i][1], 2));
                double x3 = (double) (points[i][0] + points[j][0]) / 2;
                double y3 = (double) (points[i][1] + points[j][1]) / 2;
                double centerX1 = x3 + Math.sqrt(r * r - q * q / 4) * (points[i][1] - points[j][1]) / q;
                double centerY1 = y3 + Math.sqrt(r * r - q * q / 4) * (points[j][0] - points[i][0]) / q;
                double centerX2 = x3 - Math.sqrt(r * r - q * q / 4) * (points[i][1] - points[j][1]) / q;
                double centerY2 = y3 - Math.sqrt(r * r - q * q / 4) * (points[j][0] - points[i][0]) / q;
                int circleOneCount = 0, circleTwoCount = 0;
                for (int k = 0; k < points.length; k++) {
                    if (Math.pow(centerX1 - points[k][0], 2) + Math.pow(centerY1 - points[k][1], 2) <= r * r)
                        circleOneCount++;
                    if (Math.pow(centerX2 - points[k][0], 2) + Math.pow(centerY2 - points[k][1], 2) <= r * r)
                        circleTwoCount++;
                }
                max = Math.max(max, Math.max(circleOneCount, circleTwoCount));
            }
        }
        return max;
    }
}