Submission #593027

#	Time	Username	Problem	Language	Result	Execution time	Memory
593027		hail	Mobile (BOI12_mobile)	C++17	25 / 100	1103 ms	109880 KiB

mobile

#include <bits/stdc++.h>

using namespace std;

using pld = pair<long double, long double>;
using ld = long double;

#define mp make_pair

int n;
ld l;
pld station[(int)1e6]{};

pld intercept(pld coor, ld r)
{
    ld rt_mid = pow(pow(r, 2)-pow(coor.second, 2), 0.5);
    return mp(coor.first-rt_mid, coor.first+rt_mid);
}

bool check_dist(ld r)
{
    pld ret_int;
    set<pld> intercepts;

    for(int j=0; j<n; j++)
    {
        pld i=station[j];
        if(abs(i.second)<=r)
        {    
            ret_int = intercept(i, r);
            if(ret_int.second<0 || ret_int.first>l) continue;
            else intercepts.insert(ret_int);
        }
    }

    ld start=0;

    for(auto i: intercepts)
    {
        if(i.first>start) return false;
        else start= max(start, i.second);
        if(start>=l) return true;
    }

    return false;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cout<<setprecision(11);

    cin>>n>>l;

    for(int i=0; i<n; i++)
    {
        cin>>station[i].first>>station[i].second;
    }

    ld high=2e9;
    ld low=0;
    ld mid;
    while(high-low>1e-4)
    {
        mid=(high+low)/2;
        if(check_dist(mid)) high=mid;
        else low=mid;
    }

    cout<<high;

}

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5