1453. Maximum Number of Darts Inside of a Circular Dartboard

Problem Description

In this problem, you have a square wall with a circular dartboard. You have been asked to throw darts at the wall blindfolded and each throw results are represented as an array of points in a 2D plane. The task is to find out the maximum number of points that fall within or lie on any circular dartboard of a given radius, r.

Let's have a look at an example:

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

Here all the dart throws fall on the dartboard of radius 2 unit, centered on the origin. Thus, the maximum number of points that can fit inside this circular dartboard is 4.

Approach

The given problem can be solved using a geometric approach. We generate all the pairs of the given points and find out the 2 possible centers of the maximum circle containing those two points. Later on, we check for each center's location if it holds those points or not and keep track of the maximum count of points that can be included.

To make this process easier, we can create a Point structure to represent a point in 2D coordinate space and use some geometry functions that can calculate distance, create a circle given two points.

Pseudo-code:

1. Convert given array of points into a list (vector) of Point objects.
2. For each pair of points, construct two circles where each point is on the edge of the circle.
3. For each of these circles, calculate the number of points within that circle.
4. Keep track of the maximum number of points encountered.

Now let's translate this approach into solutions in different languages:

Python Solution

1
2python
3from typing import List
4from cmath import phase, rect
5import math
6
7class Solution:
8    def numPoints(self, points: List[List[int]], r: int) -> int:
9        xs = [x + y*1j for x, y in points]
10        n = len(xs)
11
12        def test(c):
13            return sum(abs(x-c) <= r + 10**-7 for x in xs)
14        
15        def get_centers(P, Q):
16            diam = abs(P-Q)
17            M = (P + Q) / 2
18            h = (r**2 - (diam / 2)**2) ** .5
19            delta = h / diam * (Q - P) * 1j
20            return M + delta, M - delta
21        
22        res = max(test(P) for P in xs)
23        for i in range(n):
24            for j in range(i):
25                for C in get_centers(xs[i], xs[j]):
26                    res = max(res, test(C))
27        return res

Java Solution

1
2java
3public class Solution {
4    public int numPoints(int[][] points, int r) {
5        int[][] pts = points;
6        int n = pts.length;
7        int res = 1;
8        for (int i = 0; i < n; ++i) {
9            for (int j = i + 1; j < n; ++j) {
10                double cX = (pts[i][0] + pts[j][0]) / 2.0;
11                double cY = (pts[i][1] + pts[j][1]) / 2.0;
12                double x = Math.abs(cX - pts[i][0]);
13                double y = Math.abs(cY - pts[i][1]);
14                double d = Math.sqrt(x * x + y * y);
15                if (d > r) {
16                    continue;
17                }
18                double[] center = new double[]{cX, cY};
19                int count = 0;
20                for (int k = 0; k < n; ++k) {
21                    double dx = center[0] - pts[k][0], dy = center[1] - pts[k][1];
22                    if (Math.sqrt(dx*dx + dy*dy) <= r + 1e-6) {
23                        ++count;
24                    }
25                }
26                res = Math.max(res, count);
27            }
28        }
29        return res;
30    }
31}

Javascript Solution

1
2javascript
3let numPoints = function(points, r) {
4    let pointsList = points;
5    let n = pointsList.length, res = 1, x = new Array(n), y = new Array(n);
6    for (let i = 0; i < n; ++i) {
7        x[i] = pointsList[i][0]*1.0, y[i] = pointsList[i][1]*1.0;
8    }
9    for (let i = 0; i < n; ++i) {
10        for (let j = i+1; j < n; ++j) {
11            let dis = ((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
12            if (dis > 4.0*r*r) continue;
13            let ang1 = Math.atan2(y[j]-y[i], x[j]-x[i]);
14            let ang2 = Math.acos(dis/(4.0*r));
15            ang1 -= Math.PI/2.0;
16            let ang = ang1-ang2;
17            let cx = x[i] + r*Math.cos(ang), cy = y[i] + r*Math.sin(ang);
18            let tmp = 0;
19            for (let k = 0; k < n; ++k) {
20                let dx = cx - x[k], dy = cy - y[k];
21                if (dx*dx+dy*dy <= 1.0*r*r+1e-7) ++tmp;
22            }
23            res = Math.max(res, tmp);
24        }
25    }
26    return res;
27};

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int numPoints(vector<vector<int>>& points, int r) {
6    const int n = points.size();
7    int ans = 1;
8    for (int i = 0; i < n; ++i)
9      for (int j = i + 1; j < n; ++j) {
10        const auto [x1, y1] = points[i];
11        const auto [x2, y2] = points[j];
12        const double d = hypot(x1 - x2, y1 - y2);
13        for (const double delta = 0; delta <= M_PI * 2 + 1e-7; delta += M_PI * 1 / 180.0) {
14          const double x = (x1 + x2) / 2.0 + cos(delta) * sqrt(r * r - d * d / 4);
15          const double y = (y1 + y2) / 2.0 + sin(delta) * sqrt(r * r - d * d / 4);
16          int cnt = 0;
17          for (const auto& [xi, yi] : points)
18            cnt += hypot(x - xi, y - yi) < r + 1e-7;
19          ans = max(ans, cnt);
20        }
21      }
22    return ans;
23  }
24};

C# Solution

1
2csharp
3public class Solution {
4    public int NumPoints(int[][] points, int r) {
5        int n = points.Length;
6        int[] x = new int[n], y = new int[n];
7        for (int i = 0; i < n; ++i) {
8            x[i] = points[i][0]; y[i] = points[i][1];
9        }
10        int res = 1;
11        
12        for (int i = 0; i < n; ++i)
13            for (int j = 0; j < n; ++j)
14            {
15                double epsilon = 1e-7;
16                double px = (x[i] + x[j]) / 2.0, py = (y[i] + y[j]) / 2.0;
17                double dx = x[i] - x[j], dy = y[i] - y[j];
18                double d = Math.Sqrt(dx * dx + dy * dy);
19                double angle = Math.Atan2(-dx, dy); 
20                double da = Math.Acos(d / (2.0 * r));
21                int sc = 0, sc2 = 0;
22                for (int k = 0; k < n; ++k)
23                {
24                    double qx = x[k] - px, qy = y[k] - py;
25                    double h2 = qx * qx + qy * qy;
26                    if (h2 <= (double)r * r + epsilon * 2.0) sc2++;
27                    if (Math.Abs(qy * dx - qx * dy) <= r * d + epsilon &&
28                        (qx * dx + qy * dy) >= -epsilon &&
29                        (qx * dx + qy * dy) <= d * d + epsilon) sc++;
30                }
31                res = Math.Max(res, Math.Max(sc, sc2));
32            }
33        
34        return res;
35    }
36}

Ruby Solution

1
2ruby
3class Solution
4  def numPoints(points, r)
5    res, ep, n = 1, 1e-7, points.size
6    points.each_with_index do |e, i|
7      points[i] = [ e[0]*1.0, e[1]*1.0 ]
8    end
9    0.upto(n-1) do |i|
10      (i+1).upto(n-1) do |j|
11        x1, y1, x2, y2 = points[i][0], points[i][1], points[j][0], points[j][1]
12        dis = Math.sqrt((x2-x1)**2 + (y2-y1)**2)
13        next if dis > 2.0*r
14        a1 = Math.atan2(y2-y1, x2-x1)
15        a2 = Math.acos(dis/(2*r))
16        [ a1-a2, a1+a2 ].each do |a|
17          x0, y0, tmp = x1 + r*Math.cos(a), y1 + r*Math.sin(a), 0
18          0.upto(n-1) do |k|
19            dx, dy = points[k][0]-x0, points[k][1]-y0
20            tmp += 1 if dx*dx + dy*dy < r*r + ep
21          end
22          res = [res, tmp].max
23        end
24      end
25    end
26    res
27  end
28end

PHP Solution

1
2php
3function numPoints(array $points, int $r): int {
4    $n = count($points);
5    $eps = 1e-7;
6    for ($i = 0; $i < $n; $i++) {
7        for ($j = $i + 1; $j < $n; $j++) {
8            $x1 = $points[$i][0]; $y1 = $points[$i][1];
9            $x2 = $points[$j][0]; $y2 = $points[$j][1];
10            $dx = $x2 - $x1; $dy = $y2 - $y1;
11            $d = sqrt($dx*$dx + $dy*$dy);
12            if ($d > 2*$r) continue;
13            $delta = sqrt($r*$r - ($d*$d)/4);
14            $xx = ($x1 + $x2) / 2; $yy = ($y1 + $y2) / 2;
15            foreach (array([-1, 1], [1, -1]) as $p) {
16                $x = $xx + $delta*$dy*$p[0]/$d; $y = $yy + $delta*$dx*$p[1]/$d;
17                $res = 0;
18                for ($k = 0; $k < $n; $k++) {
19                    $ddx = $x - $points[$k][0]; $ddy = $y - $points[$k][1];
20                    if ($ddx*$ddx + $ddy*$ddy < $r*$r + $eps) {
21                        $res++;
22                    }
23                }
24                $out = max($out, $res);
25            }
26        }
27    }
28    return $out;
29}

Each language handles the geometric calculations slightly differently, but the principle remains the same. The code iterates over each pair of points, calculates possible circle centers, and then checks the number of points that sit inside the circle. The maximum of these counts is then returned as the result.

Solution Implementation