#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
os << "{";
int g = size(o);
for (auto i : o) os << i << ((--g) == 0 ? "" : ", ");
os << "}";
return os;
}
void _print() {
cerr << "\n";
}
template<typename T, typename ...V>
void _print(T t, V... v) {
cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}
#ifdef LOCAL
#define dbg(x...) cerr << #x << " = "; _print(x);
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif
using db = long double;
const db inf = 1e9;
const db eps = 1e-9;
struct Line {
db m, c;
db operator()(db x) {
return m * x + c;
}
db inter(const Line& b) const {
return (c - b.c) / (b.m - m);
}
};
using ptr = struct Node*;
struct Node {
Line line;
ptr l, r;
};
db query(ptr n, db x, db l = 0, db r = 1e6) {
if (!n) return inf;
db m = (r + l) / 2;
if (x <= m) return min(query(n->l, x, l, m), n->line(x));
else return min(n->line(x), query(n->r, x, m, r));
};
ptr ins(ptr n, Line cur, db l = 0, db r = 1e6) {
if (r - l < eps) return 0;
if (!n) return new Node {cur, 0, 0};
db m = (l + r) / 2;
if (cur(m) < n->line(m)) swap(cur, n->line);
bool lhs = cur(l) < n->line(l);
bool rhs = cur(r) < n->line(r);
if (lhs) n->l = ins(n->l, cur, l, m);
if (rhs) n->r = ins(n->r, cur, m, r);
return n;
}
/*
cht
*/
main() {
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
using pd = pair<db, db>;
vt<pd> pts(n);
F0R (i, n) cin >> pts[i].f >> pts[i].s;
ptr tree = 0;
for (auto [x, maxr] : pts) {
db rtrad = min(sqrtl(maxr), query(tree, x));
cout << rtrad * rtrad << endl;
db fact = (db) 1.0 / (2 * rtrad);
tree = ins(tree, {fact, - x * fact});
}
}
Compilation message
bal.cpp:91:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
91 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
10 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
1st numbers differ - expected: '247294217.0000000000', found: '247294000.0000000000', error = '217.0000000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
505 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
560 KB |
2000 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
1372 KB |
2342nd numbers differ - expected: '148.2130000000', found: '631.7930000000', error = '483.5800000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
2908 KB |
251st numbers differ - expected: '15123.0020000000', found: '15123.0000000000', error = '0.0020000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
5360 KB |
285th numbers differ - expected: '7629.0020000000', found: '7629.0000000000', error = '0.0020000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
82 ms |
6288 KB |
511th numbers differ - expected: '4494.0050000000', found: '4494.0100000000', error = '0.0050000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
8272 KB |
164th numbers differ - expected: '1698.0020000000', found: '1698.0000000000', error = '0.0020000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
10064 KB |
248th numbers differ - expected: '2694.0020000000', found: '2694.0000000000', error = '0.0020000000' |
| 2 |
Halted |
0 ms |
0 KB |
- |
