Submission #595046

#	Time	Username	Problem	Language	Result	Execution time	Memory
595046		hail	Mobile (BOI12_mobile)	C++17	90 / 100	1089 ms	32404 KiB

mobile

#include <bits/stdc++.h>

using namespace std;

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

#define mp make_pair

int n;
ld l;
vector<pld> station;

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

bool check_dist(ld r)
{
    if(r<0) return false;
    pld ret_int;
    ld from_x=0;
    /*
    auto it=lower_bound(station.begin(), station.end(), mp(-r, -1e9));
    while(it<station.end())
    {
        if((*it).first>from_x+r) return false;
        ret_int=intercept(*it, r);
        if(ret_int.first<=from_x && ret_int.second>from_x)
        {
            from_x=ret_int.second;
            if(from_x>=l) return true;
            it = upper_bound(it+1, station.end(), mp(from_x-r, 1e9));
        }
        else it++;
    }
    return false;
    */
    for(auto& circ: station)
    {
        if(circ.first>from_x+r) return false;
        if(circ.first>from_x-r)
        {
            ret_int=intercept(circ, r);
            if(ret_int.first<=from_x && ret_int.second>from_x)
            {
                from_x=ret_int.second;
                if(from_x>=l) return true;
            }
        }
        
    }

    return false;
}


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

    cout<<setprecision(20); 

    cin>>n>>l;
    station.resize(n);

    ld max_coor{};

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

    ld high=2*(max_coor+l);
    ld low=0;
    ld mid;
    while(high-low>=1e-3)
    {
        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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 0 / 5
• Subtask 19: 5 / 5
• Subtask 20: 0 / 5
• Subtask 21: 5 / 5