<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>

using ld = long double;
using ll = long long;
using pii = pair<ll,ll>;
using pdd = pair<ld,ld>;
using vi = vector<ll>;
using vp = vector<pii>;

class Solution {
public:
    vp a;
    ll n, r;

    ll sq (ll x) { return x*x; }
    ld sq (ld x) { return x*x; }

    pii mid(pii a, pii b) {
        auto [x1,y1] = a;
        auto [x2,y2] = b;
        return {(x1+x2)/2, (y1+y2)/2};
    }
    pii diff(pii a, pii b) {
        auto [x1,y1] = a;
        auto [x2,y2] = b;
        return {x2-x1, y2-y1};
    }
    pdd diff(pdd a, pdd b) {
        auto [x1,y1] = a;
        auto [x2,y2] = b;
        return {x2-x1,y2-y1};
    }
    vp ortho(pii a) {
        auto [x,y] = a;
        vp ret;
        ret.push_back({-y,x});
        ret.push_back({y,-x});
        return ret;
    }
    ld normsq(pii a) {
        auto [x,y] = a;
        return sq(x) + sq(y);
    }
    ld normsq(pdd a) {
        auto [x,y] = a;
        return sq(x) + sq(y);
    }

    ll f(pii p1, pii p2, pii o) {
        auto pm = mid(p1,p2);
        ld hsq = normsq(diff(pm,p2));
        ld lo = 0, hi = r, mul = -1;
        while (hi - lo > 1e-9) {
            ld mid = (lo+hi) / 2;
            ld bsq = normsq(make_pair(mid*o.first, mid*o.second));
            if (bsq + hsq <= r*r) {
                mul = mid;
                lo = mid;
            }
            else hi = mid;
        }
        pdd c = make_pair(pm.first + mul * o.first, pm.second + mul * o.second);

        ll ret = 2;
        for (auto p3 : a) {
            if (p3 == p1 || p3 == p2) continue;
            pdd t = {p3.first,p3.second};
            ld dsq = normsq(diff(c,t));
            if (dsq <= r*r+1e-6) ret++;
        }
        return ret;
    }

    int numPoints(vector<vector<int>>& darts, int _r) {
        n = darts.size();
        for (auto xy : darts) {
            ll x = 2*xy[0], y = 2*xy[1];
            a.push_back({x,y});
        }
        r = 2*_r;
        
        ll ans = 1;
        for (int i=0; i<n; i++) {
            pii p1 = a[i];
            for (int j=i+1; j<n; j++) {
                pii p2 = a[j];
                if (normsq(diff(p1,p2)) > sq(2*r)) continue;

                pii pm = mid(p1,p2);
                auto orth = ortho(diff(p1,pm));
                for (auto o : orth) {
                    ans = max(ans, f(p1,p2,o));
                }
            }
        }
        return ans;
        
    }
};
14600