Submission #1132082

#TimeUsernameProblemLanguageResultExecution timeMemory
1132082mrsmartypantsMobile (BOI12_mobile)C++17
100 / 100
293 ms16820 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...