Submission #1221409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221409		juaquin_remon	Mobile (BOI12_mobile)	C++20	0 / 100	258 ms	51136 KiB

mobile

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

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

struct Station {
    ld x, y2;  // guardamos y² para simplificar f_i(x) = (x−x_i)² + y_i²
};

// Calcula el punto x en el que f_j(x) = f_i(x)
// con f_k(x) = (x − x_k)² + y_k² .
// Asumimos x_j != x_i.
ld intersectX(const Station &i, const Station &j) {
    // (x−x_j)² + y_j² = (x−x_i)² + y_i²
    // → x = ((y_i² + x_i²) − (y_j² + x_j²)) / (2(x_i − x_j))
    return ((i.y2 + i.x*i.x) - (j.y2 + j.x*j.x)) / (2*(i.x - j.x));
}

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

    ll N;
    ld 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;
    }
    // Suponemos que ya vienen ordenadas por x; si no:
    // sort(a.begin(), a.end(), [](auto &A, auto &B){ return A.x < B.x; });

    // Encolamos los índices de las estaciones en el hull
    vector<int> hull;
    // Y guardamos los puntos de corte con la estación anterior en el hull
    vector<ld> cuts;
    hull.reserve(N);
    cuts.reserve(N);

    for(int i = 0; i < N; i++){
        // Eliminamos de atrás mientras la intersección
        // con el nuevo sea <= la última intersección
        while(!hull.empty()){
            int j = hull.back();
            ld xij = intersectX(a[j], a[i]);
            if(cuts.empty() || xij > cuts.back()){
                // vale, es un punto de corte válido creciente
                cuts.push_back(xij);
                break;
            }
            // si no, descartamos j
            hull.pop_back();
            cuts.pop_back();
        }
        // si el hull estaba vacío, empujamos la estación sin corte previo
        if(hull.empty()){
            hull.push_back(i);
            // usamos un “corte” ficticio = −∞ para el primer segmento
            cuts.push_back(-INF);
        } else {
            hull.push_back(i);
        }
    }

    // Ahora tenemos K = hull.size() estaciones activas y K cortes
    int K = hull.size();
    ld ans2 = 0;  // guardaremos el máximo de dist²

    for(int t = 0; t < K; t++){
        int i = hull[t];
        // Intervalo de validez de esta estación:
        // [ left, right ] ∩ [0, L]
        ld left  = t == 0     ? 0 : cuts[t];
        ld right = t+1 == K   ? L : cuts[t+1];

        // recortamos al dominio [0, L]
        left  = max(left,  (ld)0);
        right = min(right, L);

        if(left > right) continue;

        // La distancia mínima en este segmento se da siempre
        // en uno de los extremos (porque f_i es parábola convexa)
        ld dx1 = left  - a[i].x;
        ld dx2 = right - a[i].x;
        ans2 = max(ans2, dx1*dx1 + a[i].y2);
        ans2 = max(ans2, dx2*dx2 + a[i].y2);
    }

    // la respuesta es sqrt(del dist²)
    ld ans = sqrtl(ans2);
    cout << fixed << setprecision(6) << (double)ans << "\n";
    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