<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:
        n = len(darts)
        centers = set()
        for i in range(n-1):
            for j in range(i+1,n):
                l = abs(darts[i][0] - darts[j][0])
                h = abs(darts[i][1] - darts[j][1])
                dst = (l*l + h*h)**(1/2)
                if dst > 2*r:
                    continue
                elif dst == 2*r:
                    center = ((darts[i][0] + darts[j][0])/2, (darts[i][1] + darts[j][1])/2)
                    centers.add(center)
                else:
                    m = [(darts[i][0] + darts[j][0])/2, (darts[i][1] + darts[j][1])/2]
                    hdst = dst/2
                    off = (r*r - hdst*hdst)**(1/2) # scalar
                    x1 = darts[i][0] - m[0]
                    y1 = darts[i][1] - m[1]
                    if x1 != 0:
                        k = -y1/x1 
                        y2 = off/(1 + k*k)**(1/2)
                        x2 = k*y2 # voff [x2, y2] = vectorial offset
                    else: 
                        y2 = 0
                        x2 = off
                    center1 = (m[0] + x2, m[1] + y2) # m + voff
                    center2 = (m[0] - x2, m[1] - y2) # m - voff
                    centers.add(center1)
                    centers.add(center2)
        res = 1
        for cent in centers:
            num = 0
            for dart in darts:
                l = abs(cent[0] - dart[0])
                if l <= r:
                    h = abs(cent[1] - dart[1])
                    if h <= r:
                        d = (l*l + h*h)**(1/2)
                        if d <= r + 1.0e-8:
                            num += 1
            if num > res:
                res = num
        return res

18300