제출 #1202381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202381		SSKMF	Balloons (CEOI11_bal)	C++20	10 / 100	118 ms	2000 KiB

bal

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

pair <int , long double> candidati[200001];

inline long double Necesar (pair <int , long double>& anterior , const int actual)
{
    return 1LL * (actual - anterior.first) * (actual - anterior.first) / (4 * anterior.second);
}

inline long double Intersectie (pair <int , long double>& functie_1 , pair <int , long double>& functie_2)
{
    const long double factor_1 = functie_2.second - functie_1.second;
    const long double factor_2 = -2 * (functie_1.first * functie_2.second - functie_2.first * functie_1.second);
    const long double factor_3 = functie_1.first * functie_1.first * functie_2.second - functie_2.first * functie_2.first * functie_1.second;
    long double delta = factor_2 * factor_2 - 4 * factor_1 * factor_3;
    if (delta < 0) { return 0; }
    const long double candidat = (-factor_2 + sqrt(delta)) / (2 * factor_1);
    if (candidat < functie_2.first) { return 0; }
    return candidat;
}

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

    int lungime;
    cin >> lungime;

    cout << fixed << setprecision(3);

    for (int indice = 1 ; indice <= lungime ; indice++)
    {
        pair <int , long double> actual;
        cin >> actual.first >> actual.second;

        while (candidati[0].first > 1 && Necesar(candidati[candidati[0].first - 1] , actual.first) <= Necesar(candidati[candidati[0].first] , actual.first))
            { candidati[0].first--; }
            
        if (candidati[0].first)
            { actual.second = min(actual.second , Necesar(candidati[candidati[0].first] , actual.first)); }

        while (candidati[0].first > 1 && Intersectie(candidati[candidati[0].first - 1] , actual) <= Intersectie(candidati[candidati[0].first] , actual))
            { candidati[0].first--; }

        candidati[++candidati[0].first] = actual;
        cout << actual.second << '\n';
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10