1059D - Nature Reserve - CodeForces Solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define vpll vector<pair<ll, ll>>
#define vpii vector<pair<int, int>>
#define vll vector<ll>
#define si set<int>
#define sll set<ll>
#define mii map<int, int>
#define mll map<ll, ll>
#define ff first
#define ss second
#define mseti multiset<int>
#define msetll multiset<ll>
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
ll mod2 = 998244353;
ll mod1 = 1000000007;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // ios_base& scientific (ios_base& str);
    int t = 1;
    // cin>>t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<pair<double,double>> v(n);
        for (int i = 0; i < n; i++)
            cin >> v[i].ff >> v[i].ss;

        int neg = 0, pos = 0;
        for (int i = 0; i < n; i++)
        {
            neg += (v[i].ss < 0);
            pos += (v[i].ss > 0);
        }
        if (pos > 0 && neg > 0)
        {
            cout << -1 << endl;
            return 0;
        }
        else if (neg > 0)
        {
            for (int i = 0; i < n; i++)
                v[i].ss = -v[i].ss;
        }

        double l = 0, r = 1e15;
        for (int i = 0; i < n; i++)
        {
            l = max(l, v[i].ss / 2.0);
        }
        l -= 1e-6;
        while (abs(l - r) /max(abs(l),1.0)>= 1e-9)
        {
            double mid = (l + r) / 2;
            double low = v[0].ff - sqrt(2.0 * v[0].ss *(mid - v[0].ss/2.0));
            double up = v[0].ff + sqrt(2.0 * v[0].ss * mid - v[0].ss * 1.0 * v[0].ss);

            for (int i = 1; i < n; i++)
            {
                low = max(low, v[i].ff - sqrt(2.0 * v[i].ss * (mid - v[i].ss/2.0)));
                up = min(up, v[i].ff + sqrt(2.0 * v[i].ss * mid - v[i].ss * 1.0 * v[i].ss));
            }
            if(low < up){
                r = mid;
            }
            else
                l = mid;

            // cout<<fixed<<setprecision(9) << l << " " << r<<" " <<low <<" "<<up << endl;
        }
        cout <<fixed<<setprecision(9)<< r << endl;
    }

    return 0;
}