Submission #513219

#	Time	Username	Problem	Language	Result	Execution time	Memory
513219		riverwalk3	Mobile (BOI12_mobile)	C++14	0 / 100	1054 ms	31568 KiB

mobile

#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#define MAXN 1000100
using namespace std;
struct Beacon
{
    double x, y;
    Beacon()
    {
        x = y = 0;
    }
};
int N; double L;
Beacon b[MAXN];
bool judge(double R)
{
    double left_most_gap = 0;
    double l, r;
    for(int i=0; i<N; i++)
    {
        if(b[i].y > R)
        {
            continue;
        }
        else
        {
            l = b[i].x - sqrt(R*R-b[i].y*b[i].y);
            r = b[i].x + sqrt(R*R+b[i].y*b[i].y);
            if(l <= left_most_gap)
            {
                left_most_gap = max(left_most_gap, r);
            }
        }
    }
    if(left_most_gap >= L)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    cin>>N>>L;
    for(int i=0; i<N; i++)
    {
        cin>>b[i].x>>b[i].y;
    }
    double lbound = 0; double hbound = L * 1.5; double avg;
    while(hbound - lbound > 1e-3)
    {
        avg = (lbound + hbound)/2;
        if(judge(avg))
        {
            hbound = avg;
        }
        else
        {
            lbound = avg;
        }
    }
    cout<<fixed<<setprecision(3)<<avg<<endl;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 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