제출 #1252095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252095		abc	Balloons (CEOI11_bal)	C++20	10 / 100	173 ms	7500 KiB

bal

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

int MOD = 1e9+7;
double MUL = 1e-3;

bool check(double r1, double r2, double x1, double x2)
{
    double y = (r1 - r2);
    double x = (x1 - x2);
    double r = (r1 + r2);
    return (r * r) < (x * x + y * y);  // use double arithmetic
}

double get_ht(double x1, double x2, double r1)
{
    // compute in double, don't cast to float
    return ((x1 - x2) * (x1 - x2)) / (4.0 * r1);
}

int main() {
    int n;
    cin >> n;

    vector<pair<double,double>> arr(n);
    for(int i = 0; i < n; i++){
        cin >> arr[i].first >> arr[i].second;
    }

    vector<pair<double,double>> stk;
    vector<double> res(n, 0.0);
    res[0] = arr[0].second;
    stk.push_back({arr[0].first, arr[0].second});

    for(int i = 1; i < n; i++){
        double mnx = arr[i].second;

        while(!stk.empty() && !check(stk.back().second, arr[i].second, stk.back().first, arr[i].first)){
            double ht = get_ht(stk.back().first, arr[i].first, stk.back().second);
            mnx = min(mnx, ht);
            stk.pop_back();
        }

        res[i] = mnx;
        stk.push_back({arr[i].first, mnx});
    }

    for(int i = 0; i < n; i++){
        cout << fixed << setprecision(4) << res[i] << "\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