Submission #1289919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289919		becastal	Balloons (CEOI11_bal)	C++20	10 / 100	535 ms	7288 KiB

bal

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
using namespace std;

typedef double ld;
const ld DINF = 1e18;
const ld pi = acos(-1.0);
const ld eps = 1e-9;

#define sq(x) ((x)*(x))

bool eq(ld a, ld b) {
	return abs(a - b) <= eps;
}

struct pt { // ponto
	ld x, y;
	pt(ld x_ = 0, ld y_ = 0) : x(x_), y(y_) {}
	bool operator < (const pt p) const {
		if (!eq(x, p.x)) return x < p.x;
		if (!eq(y, p.y)) return y < p.y;
		return 0;
	}
	bool operator == (const pt p) const {
		return eq(x, p.x) and eq(y, p.y);
	}
	pt operator + (const pt p) const { return pt(x+p.x, y+p.y); }
	pt operator - (const pt p) const { return pt(x-p.x, y-p.y); }
	pt operator * (const ld c) const { return pt(x*c  , y*c  ); }
	pt operator / (const ld c) const { return pt(x/c  , y/c  ); }
	ld operator * (const pt p) const { return x*p.x + y*p.y; }
	ld operator ^ (const pt p) const { return x*p.y - y*p.x; }
	friend istream& operator >> (istream& in, pt& p) {
		return in >> p.x >> p.y;
	}
};

ld dist(pt p, pt q) { // distancia
	return hypot(p.y - q.y, p.x - q.x);
}

int solve() {
	int n; cin >> n;
	vector<array<int, 2>> A(n);

	for (auto& [x, r] : A) {
		cin >> x >> r;
	}

	vector<ld> R(n);

	auto intersec = [&](int i, ld ri, int j, ld rj) {
		return dist(pt(A[i][0], ri), pt(A[j][0], rj)) < (ri + rj);
	};

	stack<int> S;
	for (int i = 0; i < n; i++) {
		ld rr = A[i][1];

		while (S.size() and intersec(S.top(), R[S.top()], i, rr)) {
			ld l = 0.0, r = rr;
			for (int rep = 0; rep < 100; rep++) {
				ld mid = 0.5 * (l + r);

				if (intersec(S.top(), R[S.top()], i, mid)) {
					r = mid;
				} else {
					l = mid;
				}
			}
			rr = l;
			
			if (rr >= R[S.top()]) {
				S.pop();
			} else {
				break;
			}
		}

		R[i] = rr;
		S.push(i);
	}

	for (int i = 0; i < n; i++) {
		cout << fixed << setprecision(10) << R[i] << "\n";
	}

	return(0);
}

int main()
{
    _;

	int t = 1; //cin >> t;
	while (t--) {
		solve();
	}
    
    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