Submission #746256

#	Time	Username	Problem	Language	Result	Execution time	Memory
746256		Anonymous_Guys	Balloons (CEOI11_bal)	C++17	100 / 100	333 ms	6988 KiB

bal

// Source: https://usaco.guide/general/io

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

#define ii pair<double, double>
#define fi first
#define fou(i, a, b) for (int i = a; i <= b; ++i)
#define se second
double ans[1000009];

// nối tâm của 2 đường tròn => cạnh huyền tam giác
// tìm độ dài đoạn thẳng từ tọa độ đường tròn a đến đường tròn b => cạnh đáy
// cạnh còn lại của tam giác sẽ được tính bằng cách lấy bán kính 2 hình trừ nhau
/**
    |`
    |  `
    |____`
*/
double cal(ii a, double b) {
    double sum = (b - a.fi) * (b - a.fi * 1.00) / (4 * 1.00 * a.se);
    return sum;
}
int main() {
	int n; cin >> n;
	stack<pair<double, double>> st;

	fou(i, 1, n) {
        double x, r; cin >> x >> r;
        double kq = r;
        while(!st.empty()) {
            auto it = st.top();

            double sum = cal(it, x);
            kq = min(kq, sum);
            if (kq >= it.se) {
                st.pop();
                continue;
            } else break;
        }
        st.push({x, kq});
        ans[i] = kq;


	}
	fou(i, 1, n) cout << fixed << setprecision(3) << ans[i] << "\n"  ;
	return 0;
}

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