답안 #86946 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86946	2018-11-28T17:04:30 Z	popovicirobert	Mobile (BOI12_mobile)	C++14	0 / 100	693 ms	132096 KB

mobile

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const long double eps = 1e-9;
const long double INF = 1e18;
const int MAXN = (int) 1e6;

struct Point {
    long double x, y;
}pts[MAXN + 1];

inline long double dist(Point a, Point b) {
    return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

struct Data {
    long double l, r;
    int id;
};

vector <Data> stk;

inline bool eq(long double a, long double b) {
    return fabs(a - b) < eps;
}

long double L;

inline bool ok(long double &l, long double &r, Point b) {
    Point a = pts[stk.back().id];
    if(eq(a.x, b.x)) {
        return 0;
    }
    long double x = 1.0 * (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * (b.x - a.x));
    if(x > L) {
        return 0;
    }
    x = max(x, (long double) 0.0);
    if(x - stk.back().l > 0) {
        stk.back().r = x;
        l = x;
        r = L;
        return 0;
    }
    l = stk.back().l;
    r = L;
    return 1;
}

int main() {
    //ifstream cin("B.in");
    //ofstream cout("B.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> L;
    int sz = 0;
    for(i = 1; i <= n; i++) {
        long double x, y;
        cin >> x >> y;
        if(sz == 0) {
            pts[++sz] = {x, y};
            continue;
        }
        if(eq(x, pts[sz].x)) {
            if(pts[sz].y <= 0 && y <= 0) {
                pts[sz].y = y;
            }
            else if(pts[sz].y <= 0 && y >= 0) {
                pts[++sz].y = y;
            }
        }
        else {
            pts[++sz] = {x, y};
        }
    }
    n = sz;
    stk.push_back({0, L, 1});
    for(i = 2; i <= n; i++) {
        long double l = INF, r = -INF;
        while(!stk.empty()) {
            if(ok(l, r, pts[i])) {
                stk.pop_back();
            }
            else {
                break;
            }
        }
        if(r - l > 0) {
            stk.push_back({l, r, i});
        }
    }
    long double ans = 0;
    for(auto it : stk) {
        ans = max(ans, dist(pts[it.id], {it.l, 0}));
        ans = max(ans, dist(pts[it.id], {it.r, 0}));
    }
    cout << fixed << setprecision(20) << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	512 KB	Output is correct
4	Incorrect	2 ms	512 KB	Output isn't correct

Subtask #2
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	608 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	608 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	708 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	880 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	960 KB	Output is correct
2	Correct	5 ms	992 KB	Output is correct
3	Correct	4 ms	992 KB	Output is correct
4	Correct	7 ms	1120 KB	Output is correct
5	Incorrect	5 ms	1120 KB	Output isn't correct

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	4176 KB	Output is correct
2	Correct	61 ms	4608 KB	Output is correct
3	Correct	36 ms	5380 KB	Output is correct
4	Incorrect	54 ms	6944 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	44 ms	6944 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	15104 KB	Output is correct
2	Correct	56 ms	15104 KB	Output is correct
3	Correct	56 ms	15104 KB	Output is correct
4	Incorrect	84 ms	15104 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #10
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	15104 KB	Output is correct
2	Correct	67 ms	15104 KB	Output is correct
3	Correct	62 ms	15120 KB	Output is correct
4	Incorrect	86 ms	19280 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #11
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	92 ms	22384 KB	Output is correct
2	Correct	73 ms	22384 KB	Output is correct
3	Correct	59 ms	22384 KB	Output is correct
4	Incorrect	106 ms	25200 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #12
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	318 ms	66648 KB	Output is correct
2	Correct	322 ms	66648 KB	Output is correct
3	Correct	316 ms	66648 KB	Output is correct
4	Incorrect	393 ms	66648 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #13
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	335 ms	66648 KB	Output is correct
2	Correct	355 ms	66648 KB	Output is correct
3	Correct	287 ms	66648 KB	Output is correct
4	Incorrect	409 ms	66648 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	403 ms	95560 KB	Output is correct
2	Correct	432 ms	95560 KB	Output is correct
3	Correct	411 ms	95560 KB	Output is correct
4	Incorrect	457 ms	95560 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #15
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	449 ms	95560 KB	Output is correct
2	Correct	463 ms	95560 KB	Output is correct
3	Correct	378 ms	95560 KB	Output is correct
4	Incorrect	490 ms	95560 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #16
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	500 ms	102632 KB	Output is correct
2	Correct	477 ms	102632 KB	Output is correct
3	Correct	457 ms	102632 KB	Output is correct
4	Incorrect	593 ms	102632 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	526 ms	102632 KB	Output is correct
2	Correct	534 ms	102632 KB	Output is correct
3	Correct	408 ms	102632 KB	Output is correct
4	Incorrect	607 ms	102632 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	594 ms	105888 KB	Output is correct
2	Correct	519 ms	105888 KB	Output is correct
3	Correct	535 ms	105888 KB	Output is correct
4	Incorrect	632 ms	105888 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	564 ms	105888 KB	Output is correct
2	Correct	623 ms	105888 KB	Output is correct
3	Correct	450 ms	105888 KB	Output is correct
4	Incorrect	693 ms	105888 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #20
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	661 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

Subtask #21
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	659 ms	132096 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2	Halted	0 ms	0 KB	-

답안 #86946

Compilation message