oj.uz

Submission #746256

# Submission time Handle Problem Language Result Execution time Memory
746256 2023-05-22T04:10:43 Z Anonymous_Guys Balloons (CEOI11_bal) C++17
100 / 100
 333 ms 6988 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 10 numbers

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB 2 numbers

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB 505 numbers

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB 2000 numbers

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 748 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1988 KB 50000 numbers
2 Correct 86 ms 1892 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 3456 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 4028 KB 115362 numbers
2 Correct 193 ms 4228 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5160 KB 154271 numbers
2 Correct 325 ms 6988 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 6120 KB 200000 numbers
2 Correct 333 ms 6876 KB 199945 numbers