oj.uz

Submission #676018

# Submission time Handle Problem Language Result Execution time Memory
676018 2022-12-28T21:45:00 Z thiago_bastos Balloons (CEOI11_bal) C++17
100 / 100
 467 ms 10820 KB 
#include "bits/stdc++.h"

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second

using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;
	
struct point {
	ld x, y;
};

ld minRadius(point A, ld x0) {
	ld l = 0, r = 1e9;
	while(fabs(l - r) > EPS) {
		ld m = (l + r) / 2;
		ld x = A.x - x0, y = A.y - m;
		if(x * x + y * y <= (A.y + m) * (A.y + m)) r = m;
		else l = m;
	}
	return r;
}

void solve() {
	int n;
	vector<point> c;

	cin >> n;

	vector<int> x(n), r(n);

	for(int i = 0; i < n; ++i) cin >> x[i] >> r[i];
	
	cout.precision(3);
	cout.setf(ios_base :: fixed);

	c.pb({0.0L + x[0], 0.0L + r[0]});

	cout << 0.0L + r[0] << '\n';

	for(int i = 1; i < n; ++i) {
		ld radius = r[i];
		while(!c.empty()) {
			radius = min(radius, minRadius(c.back(), x[i]));
			if(radius <= c.back().y) break;
			c.pop_back();
		}
		c.pb({0.0L + x[i], 0.0L + radius});
		cout << radius << '\n';
	}
}		

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 864 KB 20000 numbers

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 2332 KB 50000 numbers
2 Correct 109 ms 3028 KB 49912 numbers

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 3732 KB 100000 numbers

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 4368 KB 115362 numbers
2 Correct 262 ms 6344 KB 119971 numbers

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 5540 KB 154271 numbers
2 Correct 461 ms 10820 KB 200000 numbers

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 6448 KB 200000 numbers
2 Correct 443 ms 10816 KB 199945 numbers