답안 #595049

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595049	2022-07-13T09:51:53 Z	hail	Mobile (BOI12_mobile)	C++17	90 / 100	1000 ms	16068 KB

mobile

#include <bits/stdc++.h>

using namespace std;

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

#define mp make_pair

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

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;
    */
   pld circ;
    for(int i=0; i<n; i++)
    {
        circ=station[i];
        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;

    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.0 / 4.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct

Subtask #2
4.0 / 4.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct

Subtask #3
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	340 KB	Output is correct

Subtask #4
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	3 ms	340 KB	Output is correct
3	Correct	4 ms	340 KB	Output is correct
4	Correct	4 ms	340 KB	Output is correct

Subtask #5
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	3 ms	340 KB	Output is correct
3	Correct	5 ms	340 KB	Output is correct
4	Correct	3 ms	340 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	340 KB	Output is correct
2	Correct	3 ms	340 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	3 ms	340 KB	Output is correct
5	Correct	2 ms	340 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	1428 KB	Output is correct
2	Correct	41 ms	1484 KB	Output is correct
3	Correct	31 ms	1100 KB	Output is correct
4	Correct	43 ms	1476 KB	Output is correct
5	Correct	25 ms	1056 KB	Output is correct

Subtask #8
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	1484 KB	Output is correct
2	Correct	34 ms	1364 KB	Output is correct
3	Correct	40 ms	1572 KB	Output is correct
4	Correct	44 ms	1444 KB	Output is correct
5	Correct	53 ms	1612 KB	Output is correct

Subtask #9
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	100 ms	1688 KB	Output is correct
2	Correct	43 ms	1560 KB	Output is correct
3	Correct	59 ms	1604 KB	Output is correct
4	Correct	62 ms	1820 KB	Output is correct
5	Correct	44 ms	1576 KB	Output is correct

Subtask #10
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	1852 KB	Output is correct
2	Correct	51 ms	1772 KB	Output is correct
3	Correct	62 ms	1788 KB	Output is correct
4	Correct	61 ms	1868 KB	Output is correct
5	Correct	49 ms	1852 KB	Output is correct

Subtask #11
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	1868 KB	Output is correct
2	Correct	46 ms	1816 KB	Output is correct
3	Correct	58 ms	1868 KB	Output is correct
4	Correct	63 ms	1812 KB	Output is correct
5	Correct	50 ms	1812 KB	Output is correct

Subtask #12
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	643 ms	8140 KB	Output is correct
2	Correct	241 ms	8040 KB	Output is correct
3	Correct	233 ms	8048 KB	Output is correct
4	Correct	328 ms	8056 KB	Output is correct
5	Correct	256 ms	8100 KB	Output is correct

Subtask #13
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	265 ms	8172 KB	Output is correct
2	Correct	388 ms	8064 KB	Output is correct
3	Correct	301 ms	8136 KB	Output is correct
4	Correct	315 ms	8136 KB	Output is correct
5	Correct	267 ms	8036 KB	Output is correct

Subtask #14
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	804 ms	9704 KB	Output is correct
2	Correct	293 ms	9676 KB	Output is correct
3	Correct	284 ms	9608 KB	Output is correct
4	Correct	390 ms	9744 KB	Output is correct
5	Correct	318 ms	9700 KB	Output is correct

Subtask #15
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	294 ms	9616 KB	Output is correct
2	Correct	456 ms	9868 KB	Output is correct
3	Correct	355 ms	9776 KB	Output is correct
4	Correct	395 ms	9708 KB	Output is correct
5	Correct	324 ms	9680 KB	Output is correct

Subtask #16
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	979 ms	11336 KB	Output is correct
2	Correct	341 ms	11260 KB	Output is correct
3	Correct	327 ms	11424 KB	Output is correct
4	Correct	449 ms	11176 KB	Output is correct
5	Correct	349 ms	11268 KB	Output is correct

Subtask #17
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	344 ms	11192 KB	Output is correct
2	Correct	530 ms	11164 KB	Output is correct
3	Correct	431 ms	11268 KB	Output is correct
4	Correct	495 ms	11316 KB	Output is correct
5	Correct	375 ms	11332 KB	Output is correct

Subtask #18
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1081 ms	12872 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #19
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	404 ms	12788 KB	Output is correct
2	Correct	631 ms	12836 KB	Output is correct
3	Correct	485 ms	12840 KB	Output is correct
4	Correct	501 ms	12716 KB	Output is correct
5	Correct	482 ms	12768 KB	Output is correct

Subtask #20
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1087 ms	15884 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #21
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	511 ms	15916 KB	Output is correct
2	Correct	775 ms	15936 KB	Output is correct
3	Correct	655 ms	16068 KB	Output is correct
4	Correct	630 ms	15952 KB	Output is correct
5	Correct	555 ms	15952 KB	Output is correct

답안 #595049

Compilation message