Red Zone

• Time : $O(n^2log(2e9))$
• Space : $O(n)$

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;

#define rep(i,m,n) for(ll i=m;i<n;i++)
#define sz(x) ll((x).size())

ll helper(ll r, vector<complex<ld>>& A){
    ll res = 0;
    rep(i,0,sz(A)) {
        rep(j,i+1,sz(A)) {
            auto g = A[j] - A[i];
            ld d = abs(g);
            if(d > 2 * r) continue;
            ld h = sqrt(1.*r*r - d*d/4.);
            auto m = (A[i] + A[j]); m /= 2.;
            auto p = complex<ld>(-g.imag(), g.real()) * (h / d);
            ll c1 = 2, c2 = 2;
            rep(l,0,sz(A)) {
                if(l == i or l == j) continue;
                if(abs(A[l] - (m-p)) <= r) c1++;
                if(abs(A[l] - (m+p)) <= r) c2++;
            }
            res = max({res,c2,c2});
        }
    }
    return res;
}
int Solution::solve(vector<vector<int> > &A, int B) {
    vector<complex<ld>> AA;
    rep(i,0,sz(A)) AA.push_back({1. * A[i][0], 1. * A[i][1]});
    ll l = 1, r = 2*1e9;
    while(l <= r) {
        ll m = l + (r - l) / 2;
        bool pass = helper(m,AA) >= B;
        if(pass) r = m - 1;
        else l = m + 1;
    }
    return l;
}