Submission #1330380

#TimeUsernameProblemLanguageResultExecution timeMemory
1330380randi_pavMobile (BOI12_mobile)C++20
100 / 100
345 ms95860 KiB
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <deque>

using namespace std;

typedef long double ld;

struct Tower {
    ld x, y;
};

// Find the point x where two towers are equidistant
ld intersect(Tower a, Tower b) {
    return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2.0 * (b.x - a.x));
}

ld get_dist(Tower t, ld x) {
    return sqrtl((t.x - x) * (t.x - x) + t.y * t.y);
}

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

    int n; ld l;
    cin >> n >> l;

    vector<Tower> input(n);
    for(int i=0; i<n; ++i) cin >> input[i].x >> input[i].y;

    // 1. Remove duplicate X coordinates (keep smallest |y|)
    vector<Tower> towers;
    for(auto &t : input) {
        if(!towers.empty() && towers.back().x == t.x) {
            if(abs(t.y) < abs(towers.back().y)) towers.back() = t;
        } else towers.push_back(t);
    }

    // 2. Build the Lower Envelope using a Deque
    deque<Tower> dq;
    for(auto &t : towers) {
        while(dq.size() >= 2) {
            if(intersect(dq[dq.size()-2], dq.back()) >= intersect(dq.back(), t)) 
                dq.pop_back();
            else break;
        }
        dq.push_back(t);
    }

    // 3. Trim the Deque to the highway range [0, L]
    // If the intersection of the first two towers is < 0, the first tower is useless
    while(dq.size() >= 2 && intersect(dq[0], dq[1]) <= 0) 
        dq.pop_front();
    
    // If the intersection of the last two is > L, the last tower is useless
    while(dq.size() >= 2 && intersect(dq[dq.size()-2], dq.back()) >= l) 
        dq.pop_back();

    // 4. Calculate Max Distance
    ld max_d = 0;
    
    // Check boundaries
    max_d = max(max_d, get_dist(dq.front(), 0));
    max_d = max(max_d, get_dist(dq.back(), l));

    // Check all internal intersections
    for(int i = 0; i < (int)dq.size() - 1; ++i) {
        ld x_int = intersect(dq[i], dq[i+1]);
        // We already trimmed, so x_int is guaranteed to be within [0, L]
        max_d = max(max_d, get_dist(dq[i], x_int));
    }

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

    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...