<p>Alice is throwing <code>n</code> darts on a very large wall. You are given an array <code>darts</code> where <code>darts[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> is the position of the <code>i<sup>th</sup></code> dart that Alice threw on the wall.</p>

<p>Bob knows the positions of the <code>n</code> darts on the wall. He wants to place a dartboard of radius <code>r</code> on the wall so that the maximum number of darts that Alice throws lie&nbsp;on the dartboard.</p>

<p>Given the integer <code>r</code>, return <em>the maximum number of darts that can lie on the dartboard</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_1_1806.png" style="width: 248px; height: 211px;" />
<pre>
<strong>Input:</strong> darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> Circle dartboard with center in (0,0) and radius = 2 contain all points.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/04/29/sample_2_1806.png" style="width: 306px; height: 244px;" />
<pre>
<strong>Input:</strong> darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
<strong>Output:</strong> 5
<strong>Explanation:</strong> Circle dartboard with center in (0,4) and radius = 5 contain all points except the point (7,8).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= darts.length &lt;= 100</code></li>
	<li><code>darts[i].length == 2</code></li>
	<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>All the <code>darts</code>&nbsp;are unique</li>
	<li><code>1 &lt;= r &lt;= 5000</code></li>
</ul>

class Solution:
    def numPoints(self, darts: List[List[int]], r: int) -> int:
        

        #exp: https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/solutions/636345/python-o-n3-and-o-n2logn-solution-explained-in-detail-with-pictures/
        # better pic: https://leetcode.com/problems/maximum-number-of-darts-inside-of-a-circular-dartboard/solutions/636332/cpp-o-n-3-solution-with-pictures/?envType=company&envId=facebook&favoriteSlug=facebook-six-months&role=all&status=TO_DO
        # O(N^3) O(1)
        def get_two_cir(p1, p2, r):
            (x1, y1), (x2, y2) = p1, p2

            # delta x, delta y between points
            dx, dy = x2 - x1, y2 - y1

            # dist between points
            q = math.sqrt(dx**2 + dy**2)

            # if two points are too far away, there is no such circle
            if q > 2.0*r:
                return []

            # find the halfway point
            x3, y3 = (x1+x2)/2, (y1+y2)/2

            # distance along the mirror line (the middle point of c1 and c2)
            d = math.sqrt(r**2-(q/2)**2) # d**2 + (q/2)**2 =r**2

            # One circle (left)
            c1 = [x3 - d*dy/q, y3 + d*dx/q]

            # The other circle
            c2 = [x3 + d*dy/q, y3 - d*dx/q]
            return [c1, c2]

        # now the main function
        res = 0
        n = len(darts)

        for p in range(n):
            for q in range(p+1, n):

                # Find the two candidate circle for each pair of points
                TwoCirs = get_two_cir(darts[p], darts[q], r)

                # count how many dots are inside the circle
                for center in TwoCirs: # center = TwoCirs[1]
                    cnt = 0

                    for dots in darts: # dots =points[0]
                        if (dots[0]-center[0])**2 + (dots[1]-center[1])**2 <= r**2+10**-6:
                            cnt += 1
                    res = max(res, cnt)
                        
        return res if res else 1
16700