# Maximum Number of Darts Inside of a Circular Dartboard
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-darts-inside-of-a-circular-dartboard
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
---
## Problem
Alice is throwing `n` darts on a very large wall. You are given an array `darts` where `darts[i] = [xi, yi]` is the position of the `ith` dart that Alice threw on the wall.

Bob knows the positions of the `n` darts on the wall. He wants to place a dartboard of radius `r` on the wall so that the maximum number of darts that Alice throws lie on the dartboard.

Given the integer `r`, return _the maximum number of darts that can lie on the dartboard_.

**Example 1:**

![](https://assets.glich.co/dsa/maximum-number-of-darts-inside-of-a-circular-dartboard/image0.png) 

**Input:** darts = [[-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:**

![](https://assets.glich.co/dsa/maximum-number-of-darts-inside-of-a-circular-dartboard/image1.png) 

**Input:** darts = [[-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).

**Constraints:**

* `1 <= darts.length <= 100`
* `darts[i].length == 2`
* `-104 <= xi, yi <= 104`
* All the `darts` are unique
* `1 <= r <= 5000`

# Approaches
## Iterating Through All Pairs of Points
The fundamental insight for this approach is that an optimal circle (one containing the maximum number of darts) of a fixed radius `r` will, in general, have at least two of the darts on its boundary. If an optimal circle had fewer than two darts on its boundary, it could be moved without losing any enclosed darts until its boundary touched at least two darts. This allows us to drastically reduce the search space for the circle's center. Instead of checking an infinite number of possible centers, we only need to consider circles that are defined by pairs of darts.
**Time:** O(n^3). There are two nested loops to iterate through all `O(n^2)` pairs of darts. For each pair, we find two candidate centers. For each center, we loop through all `n` darts to count how many are inside the circle. This results in a total time complexity of `O(n^2 * n) = O(n^3)`. · **Space:** O(1) extra space, as we only need a few variables to store coordinates, distances, and counts.
**Pros:** Relatively simple to understand and implement based on a clear geometric property.; Sufficiently efficient for the given constraints (`n <= 100`).
**Cons:** Its `O(n^3)` time complexity makes it less suitable for larger values of `n`.; Relies on floating-point arithmetic, which can introduce precision errors. A small epsilon value is needed for comparisons.
### Explanation
This method iterates through all unique pairs of darts. For each pair, it calculates the centers of the two possible circles of radius `r` that have both darts on their circumference. Then, for each of these two potential circles, it counts how many of the total darts fall within it. The maximum count found across all tested circles is the answer.

Here is the algorithm:

*   Initialize `maxDarts` to 1, as a single dart can always be enclosed.
*   Iterate through every possible pair of darts, `darts[i]` and `darts[j]`.
*   For each pair, calculate the distance `d` between them.
*   If `d > 2 * r`, no circle of radius `r` can contain both darts. Continue to the next pair.
*   If `d <= 2 * r`, there are two circles of radius `r` that pass through both `darts[i]` and `darts[j]`. We need to find their centers.
    *   Calculate the midpoint `M` of the line segment connecting the two darts.
    *   The distance from `M` to either center is `h = sqrt(r^2 - (d/2)^2)`.
    *   The centers lie on the perpendicular bisector of the segment, at distance `h` from `M`. Calculate the coordinates of these two centers, `C1` and `C2`.
*   For each center (`C1` and `C2`):
    *   Initialize a counter to 0.
    *   Iterate through all `n` darts and check if their distance from the current center is less than or equal to `r` (with a small tolerance for floating-point errors).
    *   Increment the counter for each dart inside the circle.
*   Update `maxDarts` with the maximum count found so far.
*   After checking all pairs, return `maxDarts`.

```java
class Solution {
    public int numPoints(int[][] darts, int r) {
        int n = darts.length;
        if (n <= 1) {
            return n;
        }
        int maxDarts = 1;
        double rDouble = (double) r;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double x1 = darts[i][0], y1 = darts[i][1];
                double x2 = darts[j][0], y2 = darts[j][1];

                double distSq = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                
                if (distSq > 4 * rDouble * rDouble + 1e-9) {
                    continue;
                }

                double mx = (x1 + x2) / 2.0;
                double my = (y1 + y2) / 2.0;
                double dist = Math.sqrt(distSq);
                double h = Math.sqrt(Math.max(0.0, rDouble * rDouble - distSq / 4.0));
                
                double dx = x2 - x1;
                double dy = y2 - y1;

                double cx1 = mx + h * dy / dist;
                double cy1 = my - h * dx / dist;
                double cx2 = mx - h * dy / dist;
                double cy2 = my + h * dx / dist;

                int count1 = 0;
                for (int k = 0; k < n; k++) {
                    double px = darts[k][0], py = darts[k][1];
                    if ((px - cx1) * (px - cx1) + (py - cy1) * (py - cy1) <= rDouble * rDouble + 1e-9) {
                        count1++;
                    }
                }
                maxDarts = Math.max(maxDarts, count1);

                int count2 = 0;
                for (int k = 0; k < n; k++) {
                    double px = darts[k][0], py = darts[k][1];
                    if ((px - cx2) * (px - cx2) + (py - cy2) * (py - cy2) <= rDouble * rDouble + 1e-9) {
                        count2++;
                    }
                }
                maxDarts = Math.max(maxDarts, count2);
            }
        }
        return maxDarts;
    }
}
```
### Algorithm
*   Initialize `maxDarts` to 1, as a single dart can always be enclosed.
*   Iterate through every possible pair of darts, `darts[i]` and `darts[j]`.
*   For each pair, calculate the distance `d` between them.
*   If `d > 2 * r`, no circle of radius `r` can contain both darts. Continue to the next pair.
*   If `d <= 2 * r`, there are two circles of radius `r` that pass through both `darts[i]` and `darts[j]`. We need to find their centers.
    *   Calculate the midpoint `M` of the line segment connecting the two darts.
    *   The distance from `M` to either center is `h = sqrt(r^2 - (d/2)^2)`.
    *   The centers lie on the perpendicular bisector of the segment, at distance `h` from `M`. Calculate the coordinates of these two centers, `C1` and `C2`.
*   For each center (`C1` and `C2`):
    *   Initialize a counter to 0.
    *   Iterate through all `n` darts and check if their distance from the current center is less than or equal to `r` (with a small tolerance for floating-point errors).
    *   Increment the counter for each dart inside the circle.
*   Update `maxDarts` with the maximum count found so far.
*   After checking all pairs, return `maxDarts`.

## Radial Sweep Algorithm
This approach refines the search by fixing one dart, say `P_i`, and assuming it lies on the boundary of the optimal circle. This assumption implies that the center of the optimal circle must lie on a circle of radius `r` centered at `P_i`. For every other dart `P_j`, we can determine the arc on this 'circle of centers' where any center would result in a dartboard that also contains `P_j`. By converting these arcs to angular intervals (events), we can use a radial sweep-line algorithm. The goal is to find the angle on the 'circle of centers' that is overlapped by the most arcs, as this corresponds to a center that covers the maximum number of darts.
**Time:** O(n^2 log n). The main loop iterates `n` times (once for each pivot dart). Inside the loop, we generate `O(n)` events for the other darts. Sorting these events takes `O(n log n)`. The final sweep takes `O(n)`. Therefore, the total complexity is `n * O(n log n) = O(n^2 log n)`. · **Space:** O(n) extra space, required to store the list of `O(n)` angular events for each pivot dart.
**Pros:** More efficient with a time complexity of `O(n^2 log n)`.; It's a standard and elegant computational geometry technique for solving this type of problem.
**Cons:** Significantly more complex to implement correctly, especially the handling of floating-point angles, normalization, and wrapped intervals.; Still relies on floating-point arithmetic and is susceptible to precision issues.
### Explanation
For each dart, we consider it a pivot. We then calculate the angular range on a circle of radius `r` around this pivot where a center would cover each of the other darts. This transforms the problem into a 1D problem of finding the point on a circle's circumference covered by the most intervals. This is a classic application of the sweep-line algorithm.

Here is the algorithm:

*   Initialize `maxDarts` to 1.
*   Iterate through each dart `P_i` and treat it as a pivot point that must lie on the boundary of an optimal circle.
*   For each pivot `P_i`, the center of a potential optimal circle must lie on a 'circle of centers' of radius `r` around `P_i`.
*   For each other dart `P_j`:
    *   Calculate the distance `d` between `P_i` and `P_j`. If `d > 2*r`, `P_j` cannot be in the same circle, so we ignore it.
    *   Otherwise, `P_j` being inside the dartboard constrains the center to a specific arc on the 'circle of centers'.
    *   Calculate the angle `alpha` of the vector from `P_i` to `P_j` using `atan2`.
    *   Calculate the half-angle `beta` of the arc, where `beta = acos(d / (2*r))`.
    *   The angular interval for the center is `[alpha - beta, alpha + beta]`.
    *   Create two events: a 'start' event at `alpha - beta` with type `+1`, and an 'end' event at `alpha + beta` with type `-1`.
*   After generating events for all `P_j` relative to `P_i`:
    *   Handle intervals that wrap around the `-PI`/`PI` boundary by keeping a separate `wrappedCount`.
    *   Sort all events by angle. When angles are equal, 'start' events (`+1`) should be processed before 'end' events (`-1`).
    *   Perform a radial sweep: Initialize a `currentDarts` counter (starting with `wrappedCount`) and iterate through the sorted events, updating the counter based on the event type. Track the maximum value of `currentDarts` seen during the sweep.
*   Update the global `maxDarts` with the maximum found for the pivot `P_i`.
*   Return `maxDarts`.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    class Event implements Comparable<Event> {
        double angle;
        int type; // +1 for start, -1 for end

        Event(double angle, int type) {
            this.angle = angle;
            this.type = type;
        }

        @Override
        public int compareTo(Event other) {
            if (Math.abs(this.angle - other.angle) > 1e-9) {
                return Double.compare(this.angle, other.angle);
            }
            // Process +1 (start) before -1 (end)
            return Integer.compare(other.type, this.type);
        }
    }

    public int numPoints(int[][] darts, int r) {
        int n = darts.length;
        if (n <= 1) return n;
        int maxDarts = 1;
        double rDouble = (double) r;

        for (int i = 0; i < n; i++) {
            List<Event> events = new ArrayList<>();
            double px1 = darts[i][0], py1 = darts[i][1];

            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                double px2 = darts[j][0], py2 = darts[j][1];
                double distSq = (px1 - px2) * (px1 - px2) + (py1 - py2) * (py1 - py2);

                if (distSq > 4 * rDouble * rDouble + 1e-9) {
                    continue;
                }

                double dist = Math.sqrt(distSq);
                double angleAlpha = Math.atan2(py2 - py1, px2 - px1);
                double angleBeta = Math.acos(dist / (2 * rDouble));

                double startAngle = angleAlpha - angleBeta;
                double endAngle = angleAlpha + angleBeta;
                
                events.add(new Event(startAngle, 1));
                events.add(new Event(endAngle, -1));
            }

            Collections.sort(events);

            int currentDarts = 1; // For the pivot point
            maxDarts = Math.max(maxDarts, currentDarts);

            for (Event e : events) {
                currentDarts += e.type;
                maxDarts = Math.max(maxDarts, currentDarts);
            }
        }
        return maxDarts;
    }
}
```
### Algorithm
*   Initialize `maxDarts` to 1.
*   Iterate through each dart `P_i` and treat it as a pivot point that must lie on the boundary of an optimal circle.
*   For each pivot `P_i`, the center of a potential optimal circle must lie on a 'circle of centers' of radius `r` around `P_i`.
*   For each other dart `P_j`:
    *   Calculate the distance `d` between `P_i` and `P_j`. If `d > 2*r`, `P_j` cannot be in the same circle, so we ignore it.
    *   Otherwise, `P_j` being inside the dartboard constrains the center to a specific arc on the 'circle of centers'.
    *   Calculate the angle `alpha` of the vector from `P_i` to `P_j`.
    *   Calculate the half-angle `beta` of the arc, where `beta = acos(d / (2*r))`.
    *   The angular interval for the center is `[alpha - beta, alpha + beta]`.
    *   Create two events: a 'start' event at `alpha - beta` with type `+1`, and an 'end' event at `alpha + beta` with type `-1`.
*   After generating events for all `P_j` relative to `P_i`:
    *   Handle intervals that wrap around the `-PI`/`PI` boundary by keeping a separate `wrappedCount`.
    *   Sort all events by angle. When angles are equal, 'start' events (`+1`) should be processed before 'end' events (`-1`).
    *   Perform a radial sweep: Initialize a `currentDarts` counter (starting with `wrappedCount`) and iterate through the sorted events, updating the counter based on the event type. Track the maximum value of `currentDarts` seen during the sweep.
*   Update the global `maxDarts` with the maximum found for the pivot `P_i`.
*   Return `maxDarts`.

# Solutions
### Java

```java
class Solution {
public
  int numPoints(int[][] points, int r) {
    int maxPoints = 1;
    int pointsCount = points.length;
    for (int i = 0; i < pointsCount; i++) {
      for (int j = i + 1; j < pointsCount; j++) {
        double[][] intersections = getIntersections(points[i], points[j], r);
        for (double[] intersection : intersections) {
          int pointsInCircle = 0;
          for (int[] point : points) {
            double distance = distance(intersection, point);
            if (distance <= r + 1 e - 5)
              pointsInCircle++;
          }
          maxPoints = Math.max(maxPoints, pointsInCircle);
        }
      }
    }
    return maxPoints;
  }
public
  double[][] getIntersections(int[] point1, int[] point2, int radius) {
    int squaredDistance = squaredDistance(point1, point2);
    if (squaredDistance > radius * radius * 4)
      return new double[0][2];
    else if (squaredDistance == radius * radius * 4) {
      double[] intersection = new double[2];
      for (int i = 0; i < 2; i++)
        intersection[i] = (point1[i] + point2[i]) / 2.0;
      double[][] intersections = new double[1][2];
      intersections[0] = intersection;
      return intersections;
    } else {
      double[] midPoint = new double[2];
      for (int i = 0; i < 2; i++)
        midPoint[i] = (point1[i] + point2[i]) / 2.0;
      double remaining = Math.sqrt(radius * radius - squaredDistance / 4.0);
      int difference1 = point1[1] - point2[1];
      int difference2 = point2[0] - point1[0];
      double radian = Math.atan(1.0 * difference2 / difference1);
      double[] intersection0 = {midPoint[0] + remaining * Math.cos(radian),
                                midPoint[1] + remaining * Math.sin(radian)};
      double[] intersection1 = {midPoint[0] - remaining * Math.cos(radian),
                                midPoint[1] - remaining * Math.sin(radian)};
      double[][] intersections = new double[2][2];
      intersections[0] = intersection0;
      intersections[1] = intersection1;
      return intersections;
    }
  }
public
  int squaredDistance(int[] point1, int[] point2) {
    return (point2[0] - point1[0]) * (point2[0] - point1[0]) +
           (point2[1] - point1[1]) * (point2[1] - point1[1]);
  }
public
  double distance(double[] point1, int[] point2) {
    return Math.sqrt((point2[0] - point1[0]) * (point2[0] - point1[0]) +
                     (point2[1] - point1[1]) * (point2[1] - point1[1]));
  }
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/ // Time: O(N^3) // Space: O(1) class Solution { inline double dist ( const vector < double > & a , const vector < double > & b ) { return sqrt ( pow ( a [ 0 ] - b [ 0 ], 2 ) + pow ( a [ 1 ] - b [ 1 ], 2 )); } vector < double > getPoint ( const vector < double > & a , const vector < double > & b , double p , double q ) { double x = ( a [ 1 ] - b [ 1 ] + b [ 0 ] * q - a [ 0 ] * p ) / ( q - p ); double y = a [ 1 ] + p * ( x - a [ 0 ]); return { x , y }; } vector < vector < double >> getCenters ( const vector < double > & a , const vector < double > & b , int r ) { double d = dist ( a , b ); if ( d > 2 * r ) return {}; if ( d == 2 * r ) return { { ( a [ 0 ] + b [ 0 ]) / 2 , ( a [ 1 ] + b [ 1 ]) / 2 } }; double theta = acos ( d / 2 / r ); double alpha = atan2 ( a [ 1 ] - b [ 1 ], a [ 0 ] - b [ 0 ]); double p = tan ( alpha + theta ), q = tan ( alpha - theta ); return { getPoint ( a , b , p , q ), getPoint ( a , b , q , p ) }; } public: int numPoints ( vector < vector < int >>& A , int r ) { int N = A . size (), ans = 0 ; for ( int i = 0 ; i < N ; ++ i ) { for ( int j = 0 ; j < N ; ++ j ) { for ( auto & center : getCenters ({( double ) A [ i ][ 0 ], ( double ) A [ i ][ 1 ]}, {( double ) A [ j ][ 0 ], ( double ) A [ j ][ 1 ]}, r )) { int cnt = 0 ; for ( auto & p : A ) { cnt += dist ( center , {( double ) p [ 0 ], ( double ) p [ 1 ]}) <= r + 0.00001 ; } ans = max ( ans , cnt ); } } } return ans ; } };
```

### Python

```python
class Solution:
    def numPoints(self, darts: list[list[int]], r: int) -> int: def countDarts(x, y): count = 0 for x1, y1 in darts: if dist((x, y), (x1, y1)) <= r + 1e-7: count += 1 return count def possibleCenters(x1, y1, x2, y2): dx, dy = x2 - x1, y2 - y1 d = sqrt(dx * dx + dy * dy) if d > 2 * r: return [] mid_x, mid_y = (x1 + x2) / 2, (y1 + y2) / 2 dist_to_center = sqrt(r * r - (d / 2) * (d / 2)) offset_x = dist_to_center * dy / d offset_y = dist_to_center * - dx / d return [(mid_x + offset_x, mid_y + offset_y), (mid_x - offset_x, mid_y - offset_y), ] n = len(darts) max_darts = 1 for i in range(n): for j in range(i + 1, n): centers = possibleCenters(darts[i][0], darts[i][1], darts[j][0], darts[j][1]) for center in centers: max_darts = max(max_darts, countDarts(center[0], center[1])) return max_darts

```