Code Implementation

import math

class Solution:
    def numPoints(self, points, r):
        n = len(points)
        ans = 1
        for i in range(n):
            for j in range(i+1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                d = math.hypot(x1 - x2, y1 - y2)
                if d > 2 * r:
                    continue
                # Find the centers of the circles passing through both points
                midx = (x1 + x2) / 2
                midy = (y1 + y2) / 2
                angle = math.atan2(y2 - y1, x2 - x1)
                h = math.sqrt(r * r - (d / 2) ** 2)
                dx = h * math.cos(angle + math.pi / 2)
                dy = h * math.sin(angle + math.pi / 2)
                for sign in [1, -1]:
                    cx = midx + sign * dx
                    cy = midy + sign * dy
                    count = 0
                    for x, y in points:
                        if (x - cx) ** 2 + (y - cy) ** 2 <= r * r + 1e-8:
                            count += 1
                    ans = max(ans, count)
        return ans
      

#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

class Solution {
public:
    int numPoints(vector<vector<int>>& points, int r) {
        int n = points.size();
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                double x1 = points[i][0], y1 = points[i][1];
                double x2 = points[j][0], y2 = points[j][1];
                double dx = x2 - x1, dy = y2 - y1;
                double d = hypot(dx, dy);
                if (d > 2 * r) continue;
                double mx = (x1 + x2) / 2.0, my = (y1 + y2) / 2.0;
                double h = sqrt(r * r - (d / 2) * (d / 2));
                double angle = atan2(dy, dx);
                for (int sign : {1, -1}) {
                    double cx = mx + sign * h * cos(angle + M_PI / 2.0);
                    double cy = my + sign * h * sin(angle + M_PI / 2.0);
                    int count = 0;
                    for (auto& p : points) {
                        double dist2 = (p[0] - cx) * (p[0] - cx) + (p[1] - cy) * (p[1] - cy);
                        if (dist2 <= r * r + 1e-8) count++;
                    }
                    ans = max(ans, count);
                }
            }
        }
        return ans;
    }
};
      

import java.util.*;

class Solution {
    public int numPoints(int[][] points, int r) {
        int n = points.length;
        int ans = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                double x1 = points[i][0], y1 = points[i][1];
                double x2 = points[j][0], y2 = points[j][1];
                double dx = x2 - x1, dy = y2 - y1;
                double d = Math.hypot(dx, dy);
                if (d > 2 * r) continue;
                double mx = (x1 + x2) / 2.0, my = (y1 + y2) / 2.0;
                double h = Math.sqrt(r * r - (d / 2) * (d / 2));
                double angle = Math.atan2(dy, dx);
                for (int sign : new int[]{1, -1}) {
                    double cx = mx + sign * h * Math.cos(angle + Math.PI / 2.0);
                    double cy = my + sign * h * Math.sin(angle + Math.PI / 2.0);
                    int count = 0;
                    for (int[] p : points) {
                        double dist2 = (p[0] - cx) * (p[0] - cx) + (p[1] - cy) * (p[1] - cy);
                        if (dist2 <= r * r + 1e-8) count++;
                    }
                    ans = Math.max(ans, count);
                }
            }
        }
        return ans;
    }
}
      

var numPoints = function(points, r) {
    let n = points.length;
    let ans = 1;
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            let x1 = points[i][0], y1 = points[i][1];
            let x2 = points[j][0], y2 = points[j][1];
            let dx = x2 - x1, dy = y2 - y1;
            let d = Math.hypot(dx, dy);
            if (d > 2 * r) continue;
            let mx = (x1 + x2) / 2, my = (y1 + y2) / 2;
            let h = Math.sqrt(r * r - (d / 2) * (d / 2));
            let angle = Math.atan2(dy, dx);
            for (let sign of [1, -1]) {
                let cx = mx + sign * h * Math.cos(angle + Math.PI / 2);
                let cy = my + sign * h * Math.sin(angle + Math.PI / 2);
                let count = 0;
                for (let [x, y] of points) {
                    if ((x - cx) ** 2 + (y - cy) ** 2 <= r * r + 1e-8)
                        count++;
                }
                ans = Math.max(ans, count);
            }
        }
    }
    return ans;
};
      

Problem Description

You are given a list of points on a 2D plane, where each point represents the coordinates of a dart that has landed on a dartboard. You are also given an integer r representing the radius of a circular dartboard. The goal is to determine the maximum number of darts that can fit inside or on the boundary of any circle of radius r on the plane.

• You can move the circle anywhere on the plane.
• The circle does not need to be centered at any of the given points.
• You must count the maximum number of points that can be enclosed within or on the boundary of such a circle.

Constraints:

• There may be multiple valid solutions (i.e., more than one circle with the same maximum).
• You should not reuse points in a way that violates their fixed positions.
• The number of points is small (≤ 100), making brute-force approaches feasible.
• Input: points (list of [x, y] pairs), r (integer radius)
• Output: Integer representing the maximum number of darts that can fit inside a circle of radius r.

Thought Process

At first glance, you might think about trying every possible circle on the plane, but since the circle can be anywhere and the points are arbitrary, this is not practical. Instead, notice that for a circle of radius r to cover the most points, it's likely to be "anchored" by one or two of the given points (i.e., those points lie on its boundary).

• If you choose any two points, you can try to construct a circle of radius r that passes through both points. There can be zero, one, or two such circles.
• For each such circle, count how many points fall inside or on the circle.
• Repeat for all pairs of points, and also consider each single point as the center (since all points within radius r of that point are valid).

This approach is brute-force but feasible due to the small input size. As you optimize, you realize that you only need to check circles defined by pairs of points, not every possible center.

Solution Approach

• Step 1: For each pair of points, determine if a circle of radius r can pass through both. If the distance between the points is greater than 2r, it's impossible.
• Step 2: If possible, compute the centers of the two circles of radius r that pass through both points. This is a geometry problem:
  • Find the midpoint between the two points.
  • Compute the distance from this midpoint to the center(s) using the Pythagorean theorem.
  • There are two possible centers for each pair (on either side of the line connecting the points).
• Step 3: For each computed center, count how many points fall inside or on the circle (distance ≤ r).
• Step 4: Keep track of the maximum count found for any center.
• Step 5: Optionally, for completeness, check each point as a center (since all points within r of it could be covered), but this is usually covered by the above process.

The core idea is to use geometry to efficiently generate all possible circles that could potentially cover the maximum number of darts, and count for each.

Example Walkthrough

Sample Input:
points = [[1,2],[3,4],[5,6],[7,8]], r = 2

1. Start by picking pairs: (1,2)-(3,4), (1,2)-(5,6), etc.
2. For (1,2)-(3,4): Compute the distance ≈ 2.828. Since 2.828 < 4, a circle of radius 2 can go through both.
3. Compute the two possible centers for such a circle using the midpoint and perpendicular offset.
4. For each center, count how many points are within radius 2. Suppose one center covers (1,2), (3,4), and (5,6).
5. Continue for all pairs, updating the maximum count found.
6. After all pairs, the answer is the highest count found, e.g., 3.

This process ensures you don't miss any configuration that could cover more points.

Time and Space Complexity

• Brute-force: Try every possible center on the plane, which is infinite and not feasible.
• Optimized Approach:
  • There are O(N²) pairs of points.
  • For each pair, you compute up to 2 centers, and for each, you check all N points to see if they're inside the circle.
  • Total time: O(N³)
  • Space: O(1) extra (not counting input), as we only keep track of the max count and some temporary variables.
• Why O(N³)? For each of O(N²) pairs, you check O(N) points for coverage.

Summary

The solution leverages geometry to efficiently find all possible circles of a given radius that could cover the most darts. By focusing on circles defined by pairs of points and checking coverage for each, we avoid the impossible task of trying every center on the plane. The approach is both elegant and practical for small inputs, combining mathematical insight with brute-force enumeration in a controlled way.