Submission #1330374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1330374		randi_pav	Mobile (BOI12_mobile)	C++20	0 / 100	238 ms	40732 KiB

mobile

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

struct Station {
    double x, y;
};

// Calculate the x-coordinate where two stations are equidistant to the highway
double intersect(Station s1, Station s2) {
    return (s2.x * s2.x + s2.y * s2.y - s1.x * s1.x - s1.y * s1.y) / (2.0 * (s2.x - s1.x));
}

// Distance from station to a point (x, 0) on the highway
double dist(Station s, double x) {
    return sqrt((s.x - x) * (s.x - x) + s.y * s.y);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    double L;
    cin >> N >> L;

    vector<Station> input;
    for (int i = 0; i < N; ++i) {
        double xi, yi;
        cin >> xi >> yi;
        // If x is same, keep only the one closer to y=0
        if (!input.empty() && input.back().x == xi) {
            if (abs(yi) < abs(input.back().y)) input.back().y = yi;
        } else {
            input.push_back({xi, yi});
        }
    }

    vector<Station> stack;
    for (const auto& s : input) {
        while (stack.size() >= 2) {
            if (intersect(stack[stack.size() - 2], stack.back()) >= intersect(stack.back(), s)) {
                stack.pop_back();
            } else {
                break;
            }
        }
        stack.push_back(s);
    }

    double max_d = 0;
    // Check start and end of the highway
    max_d = max(max_d, dist(stack[0], 0.0));
    max_d = max(max_d, dist(stack.back(), L));

    // Check all intersection points that fall within [0, L]
    for (int i = 0; i < (int)stack.size() - 1; ++i) {
        double x_int = intersect(stack[i], stack[i+1]);
        if (x_int > 0 && x_int < L) {
            max_d = max(max_d, dist(stack[i], x_int));
        }
    }

    cout << fixed << setprecision(6) << max_d << endl;

    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