Submission #86948

#	Time	Username	Problem	Language	Result	Execution time	Memory
86948		popovicirobert	Mobile (BOI12_mobile)	C++14	100 / 100	761 ms	73652 KiB

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 double eps = 1e-9;
const double INF = 1e18;
const int MAXN = (int) 1e6;

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

inline 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 {
    double l, r;
    int id;
};

vector <Data> stk;

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

double L;

inline bool ok(double &l, double &r, Point b) {
    Point a = pts[stk.back().id];
    if(eq(a.x, b.x)) {
        return 0;
    }
    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, (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++) {
        double x, y;
        cin >> x >> y;
        y = fabs(y);
        if(sz > 0 && eq(x, pts[sz].x)) {
            pts[sz].y = min(pts[sz].y, y);
        }
        else {
            pts[++sz] = {x, y};
        }
    }
    n = sz;
    stk.push_back({0, L, 1});
    for(i = 2; i <= n; i++) {
        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});
        }
    }
    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: 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: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5