Formatted question description: https://leetcode.ca/all/1453.html

# 1453. Maximum Number of Darts Inside of a Circular Dartboard

## Level

Hard

## Description

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`

## Solution

For each `point`

in `points`

, use `point`

as the center and `r`

as the radius to draw a circle. Then for each pair of points in `points`

, calculate the intersection points of the two circles. For each intersection point, draw a circle with radius `r`

and count the number of points within or lie on the circle. During the process, store the maximum number of points within or lie on the circles. Finally, return the maximum number of points.

The precision needs to be considered. To determine whether the distance between two points is less than or equal to `r`

, use `r + 1e-5`

instead since one of the points is represented in data type `double`

.

```
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 + 1e-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]));
}
}
```