Problem statement

https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/

Solution

There is O(n^4) solution, where for each 3 points we construct circumcenter and then check how many point will be in circle with this center and radius r. There is also O(n^3) solution, where we consider only O(n^2) points which are intersections of circles with centers in given points and radii r. Why it is enough? Because each circular dartboard can be shifted such that it has at least 2 points on its border.

Finally, there is O(n^2 log n) angular sweep solution. For each point A we want to consider circles with radius r, which pass through A. We can look at center of this circle and consider at most 2n-2 points, where this circle go through one of the other points (it can be less than 2n-2 if points are far). Then we sort these points in polar coordinates and then we traverse all these points and add +1 when we start some circle and add -1 when we finish it. So at each moment of time we keep number of active points. It is quite difficult to understand without images (because this is geometry).

Complexity

Time complexity is O(n^2 log n), space complexity is O(n).

Code

class Solution:
    def DistSquare(self, Ax, Ay, Bx, By):
        return (Ax - Bx)*(Ax - Bx) + (Ay - By) * (Ay - By)
    
    def numPoints(self, points, r):
        N, P, MaxPoint = len(points), points, 1
        
        for x0, y0 in points:           
            list_sweep = []
            for x1, y1 in points:
                temp_dist = self.DistSquare(x0, y0, x1, y1)
                if temp_dist <= 4*r*r and temp_dist > 0.001:
                    alpha = atan2(y1 - y0, x1 - x0)
                    beta = acos(sqrt(temp_dist)/2/r)
                    list_sweep.append([alpha - beta, -1])
                    list_sweep.append([alpha + beta, 1])
            
            if list_sweep:
                list_sweep.sort()
                MaxPoint = max(MaxPoint, -min(accumulate([i[1] for i in list_sweep])) + 1)
                    
        return MaxPoint