Submission #1132082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132082		mrsmartypants	Mobile (BOI12_mobile)	C++17	100 / 100	293 ms	16820 KiB

mobile

#include <bits/stdc++.h>
using namespace std;

struct Point {
    double x, y;

    Point() : x(0), y(0) {}

    Point(double x, double y) : x(x), y(y) {}
};

// Function to calculate the critical point
double criticalPoint(Point a, Point b) {
    return (a.x * a.x - b.x * b.x + a.y * a.y - b.y * b.y) / (2 * (a.x - b.x));
}

// Function to calculate the distance between two points
double dist(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, L;
    cin >> N >> L;

    deque<Point> needed; 

    for (int i = 0; i < N; i++) {
        Point cur;
        cin >> cur.x >> cur.y;
        if (cur.y < 0) cur.y = -cur.y; // Treat negative y the same as positive y

        // Remove points with the same x-coordinate but further away y-coordinates
        if (!needed.empty() && needed.back().x == cur.x) {
            if (cur.y >= needed.back().y) {
                continue;
            } else {
                needed.pop_back();
            }
        }

        // Find the crosses
        while (needed.size() > 1 && criticalPoint(needed[needed.size() - 2], needed.back()) > criticalPoint(needed.back(), cur)) {
            needed.pop_back();
        }

        needed.push_back(cur);
    }

    // Remove points from the front that have critical points less than 0
    while (needed.size() > 1 && criticalPoint(needed[0], needed[1]) < 0) {
        needed.pop_front();
    }

    // Remove points from the back that exceed the length L
    while (needed.size() > 1 && criticalPoint(needed[needed.size() - 2], needed.back()) > L) {
        needed.pop_back();
    }

    double ans = 0;

    // Loop over the points and calculate the maximum distance
    for (int x = 0; x < needed.size(); x++) {
        Point left(0, 0);
        Point right(L, 0);

        if (x > 0) left.x = criticalPoint(needed[x], needed[x - 1]);
        if (x < needed.size() - 1) {
            right.x = criticalPoint(needed[x], needed[x + 1]);
        }

        // If points are out of bounds, skip
        if (left.x < 0 || right.x > L || right.x < 0 || left.x > L) continue;

        // Update the answer with the maximum distance
        ans = max(ans, max(dist(needed[x], left), dist(needed[x], right)));
    }

    cout << fixed << ans << "\n";

    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