Submission #1095252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095252		buzdi	Mobile (BOI12_mobile)	C++17	0 / 100	320 ms	71608 KiB

mobile

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define ll long long

using namespace std;

const int NMAX = 1e6;
const long double EPS = 1e-3;

struct Point {
    long double x, y;
    void read() {
        cin >> x >> y;
    }
}points[NMAX + 1];

int n, l, ind_st, i;
long double answer;
pair<int, long double> st[NMAX + 1];

long double Square(long double x) {
    return x * x;
}

long double Distance(Point p1, Point p2) {
    return sqrt(Square(p1.x - p2.x) + Square(p1.y - p2.y));
}

long double WhereBetter(Point p1, Point p2) {
    return (long double)(Square(p2.x) + Square(p2.y) - Square(p1.x) - Square(p1.y)) / (long double)(2 * (p2.x - p1.x));
}

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

    cin >> n >> l;
    for (int i = 1; i <= n; i++) {
        points[i].read();
    }

    i = 1;
    while (i <= n) {
        Point best_point = points[i];
        int pos_best_point = i;
        i++;
        while (i <= n && points[i].x == points[i - 1].x) {
            if (abs(points[i].y) < best_point.y) {
                best_point = points[i];
                pos_best_point = i;
            }
            i++;
        }

        if (ind_st >= 1 && WhereBetter(best_point, points[st[ind_st].first]) > l) {
            continue;
        }

        while (ind_st >= 1 && WhereBetter(best_point, points[st[ind_st].first]) < st[ind_st].second) {
            ind_st--;
        }

        if (ind_st == 0) {
            st[++ind_st] = { pos_best_point, 1 };
        }
        else {
            long double x = WhereBetter(best_point, points[st[ind_st].first]);
            st[++ind_st] = { pos_best_point, x };
        }
    }
    //for (int i = 1; i <= n; i++) {
    //    if (ind_st >= 1 && points[i].x == points[st[ind_st].first].x) {
    //        continue;
    //    }

    //    if (ind_st >= 1 && WhereBetter(points[i], points[st[ind_st].first]) > l) {
    //        continue;
    //    }

    //    while (ind_st >= 1 && WhereBetter(points[i], points[st[ind_st].first]) < st[ind_st].second) {
    //        ind_st--;
    //    }

    //    if (ind_st == 0) {
    //        st[++ind_st] = { i, 1 };
    //    }
    //    else {
    //        long double x = WhereBetter(points[i], points[st[ind_st].first]);
    //        st[++ind_st] = { i, x };
    //    }
    //}

    for (int i = 1; i <= ind_st; i++) {
        answer = max(answer, max(Distance(points[st[i].first], { st[i].second, 0 }), Distance(points[st[i].first], { (i == ind_st ? l : st[i + 1].second - EPS), 0 })));
    }
    cout << fixed << setprecision(6) << answer << '\n';

    return 0;
}

• 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