제출 #443109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443109		prvocislo	Balloons (CEOI11_bal)	C++17	20 / 100	707 ms	8976 KiB

bal

// aww geometria !! :)
#include <bits/stdc++.h>
typedef long double ld;
using namespace std;

const ld eps = 1e-6;
ld maxr(ld x1, ld r1, ld x2, ld r2)
{
    ld lo = 0., hi = r2;
    while (abs(lo - hi) > eps)
    {
        ld mi = (lo + hi) / 2.;
        ld xdif = x2-x1, ydif = abs(r1 - mi);
        ld prepona = sqrt(xdif*xdif+ydif*ydif);
        if (prepona < r1 + mi) // jeden az dva priesecnik, mozeme ist nizsie
            hi = mi;
        else lo = mi;
    }
    return (lo + hi) / 2.;
}
bool eq(ld x, ld y) { return abs(x - y) < eps; }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    cout << fixed << setprecision(3);
    int n;
    cin >> n;
    vector<ld> x(n), r(n);
    vector<int> st;
    for (int i = 0; i < n; i++)
    {
        cin >> x[i] >> r[i];
        while (st.size() > 1 && maxr(x[st.back()], r[st.back()], x[i], r[i]) > maxr(x[st[st.size() - 2]], r[st[st.size() - 2]], x[i], r[i]))
            st.pop_back();
        if (!st.empty()) r[i] = min(r[i], maxr(x[st.back()], r[st.back()], x[i], r[i]));
        st.push_back(i);
    }
    for (int i = 0; i < n; i++) cout << r[i] << "\n";
    return 0;
}

• Subtask 1: 10 / 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