Submission #1221414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221414		juaquin_remon	Mobile (BOI12_mobile)	C++20	100 / 100	402 ms	55388 KiB

mobile

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

using ll = long long;
using ld = long double;
const ld INF = 1e30L;

// Cada estación i define la función f_i(x) = (x - x_i)^2 + y_i^2.
// Queremos el máximo, sobre x∈[0,L], de min_i sqrt(f_i(x)).
// Equivalente a sqrt( max_x min_i f_i(x) ).

struct Station {
    ld x;
    ld y2;  // guardamos y_i^2
};

// Intersección en x donde f_i(x) = f_j(x)
ld intersectX(const Station &i, const Station &j) {
    // (x−x_i)^2 + y_i^2 = (x−x_j)^2 + y_j^2
    // → x = ( (y_j² + x_j²) - (y_i² + x_i²) ) / (2*(x_j - x_i))
    return ((j.y2 + j.x*j.x) - (i.y2 + i.x*i.x)) / (2*(j.x - i.x));
}

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

    ll N, L;
    cin >> N >> L;
    vector<Station> a(N);
    for(int i = 0; i < N; i++){
        ll xi, yi;
        cin >> xi >> yi;
        a[i].x  = xi;
        a[i].y2 = (ld)yi * yi;
    }
    // Ya vienen ordenadas por x

    // Hull almacenará índices de estaciones cuya parábola
    // aparece en la envolvente inferior cuando barrimos x.
    vector<int> hull;
    // cuts[t] = abscisa donde estación hull[t] deja de ser la más cercana
    vector<ld> cuts;

    for(int i = 0; i < N; i++){
        // Incorporamos i, eliminando por atrás
        while(!hull.empty()){
            int j = hull.back();
            ld xcut = intersectX(a[j], a[i]);
            // Si el corte con i es ≤ al corte previo, j nunca será útil
            if(cuts.empty() || xcut > cuts.back()){
                cuts.push_back(xcut);
                break;
            }
            hull.pop_back();
            cuts.pop_back();
        }
        // Si el hull quedó vacío, ponemos un corte −∞ para el primero
        if(hull.empty()){
            hull.push_back(i);
            cuts.push_back(-INF);
        } else {
            hull.push_back(i);
        }
    }

    // Ahora recorramos cada tramo [cuts[t], cuts[t+1]]∩[0,L]
    ld best2 = 0;
    int K = hull.size();
    for(int t = 0; t < K; t++){
        int i = hull[t];
        ld left  = (t == 0   ?  0 : cuts[t]);
        ld right = (t+1==K ? L : cuts[t+1]);

        if(right < 0 || left > L) continue;
        left  = max(left,  (ld)0);
        right = min(right, (ld)L);
        if(left > right) continue;

        // f_i(x) es convexa, su máximo en [left,right] está en un extremo
        ld dx1 = left  - a[i].x;
        ld dx2 = right - a[i].x;
        best2 = max(best2, dx1*dx1 + a[i].y2);
        best2 = max(best2, dx2*dx2 + a[i].y2);
    }

    cout << fixed << setprecision(6)
         << sqrtl(best2) << "\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