1453. Maximum Number of Darts Inside of a Circular Dartboard

Description

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:

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:

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

 

Solutions

Solution: Math

• Time complexity: O(n³)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[][]} darts
 * @param {number} r
 * @return {number}
 */
const numPoints = function (darts, r) {
  const getDistance = (x1, x2, y1, y2) => {
    return Math.hypot((x1 - x2), (y1 - y2));
  };

  const getCircularCenters = (x1, x2, y1, y2) => {
    const distance = getDistance(x1, x2, y1, y2);

    if (distance > r * 2) return [];
    const mx = (x1 + x2) / 2;
    const my = (y1 + y2) / 2;
    const h = Math.sqrt(r ** 2 - (distance / 2) ** 2);
    const dx = (x2 - x1) / distance;
    const dy = (y2 - y1) / distance;
    const center1 = { cx: mx - h * dy, cy: my + h * dx };
    const center2 = { cx: mx + h * dy, cy: my - h * dx };

    return [center1, center2];
  };

  const n = darts.length;
  let result = 1;

  for (let a = 0; a < n - 1; a++) {
    const [x1, y1] = darts[a];

    for (let b = a + 1; b < n; b++) {
      const [x2, y2] = darts[b];
      const centers = getCircularCenters(x1, x2, y1, y2);

      for (const { cx, cy } of centers) {
        let points = 0;

        for (const [x, y] of darts) {
          const distance = getDistance(x, cx, y, cy);

          points += distance <= r ? 1 : 0;
        }

        result = Math.max(points, result);
      }
    }
  }

  return result;
};