#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 3e3 + 5;
const int mod = 1e9 + 7;
int check(long double a, long double x, long double b, long double y)
{
return (a + b) * (a + b) >= (a - b) * (a - b) + (x - y) * (x - y);
}
long double findr(long double x, long double b, long double y)
{
long double l = 0, r = 100000;
while (r - l > 0.000001)
{
long double mid = (l + r) / 2;
if (check(mid, x, b, y)) r = mid;
else l = mid;
}
return l;
}
void _()
{
int n;
cin >> n;
long double x[n], r[n];
for (int i = 0; i < n; i++) cin >> x[i] >> r[i];
vector<array<long double, 2>> v;
for (int i = 0; i < n; i++)
{
while (!v.empty())
{
r[i] = min(r[i], findr(x[i], v.back()[0], v.back()[1]));
if (r[i] >= v.back()[0]) v.pop_back();
else break;
}
v.push_back({r[i], x[i]});
}
cout.precision(3);
for (int i = 0; i < n; i++) cout << fixed << r[i] << ' ';
cout << '\n';
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) _();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |