maximum-number-of-darts-inside-of-a-circular-dartboard

< Previous 　　　　　　　　　　　　　　　　 Next >

1453. Maximum Number of Darts Inside of a Circular Dartboard (Hard)

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 lies 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
• 1 <= r <= 5000

Related Topics

[Array] [Math] [Geometry]

Hints

Hint 1

If there is an optimal solution, you can always move the circle so that two points lie on the boundary of the circle.

Hint 2

When the radius is fixed, you can find either 0 or 1 or 2 circles that pass two given points at the same time.

Hint 3

Loop for each pair of points and find the center of the circle, after that count the number of points inside the circle.