This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
using namespace std;
const ll mod = 1e9 + 7;
struct coord_t {
ld x, y;
};
bool all(ld rad, ld l, vector<coord_t>& towers) {
ld cur = 0, radsq = rad * rad;
for (auto& t : towers) {
if (t.y > rad) continue;
ld horiz = sqrt(radsq - (t.y * t.y));
if (t.x - horiz > cur) continue;
cur = max(cur, t.x + horiz);
}
return cur >= l;
}
int main() {
// ifstream cin("valleys.in");
// ofstream cout("valleys.out");
ld n, L, i, tx, ty;
cin >> n >> L;
vector<coord_t> towers(n);
for (i = 0; i < n; i++) {
cin >> tx >> ty;
towers[i] = {tx, ty};
}
ld l = 0, r = 2e9, tol = 0.000001;
while (l < r - tol) {
ld mid = (l + r) / 2;
if (not all(mid, L, towers)) l = mid;
else r = mid - tol;
}
cout << setprecision(10) << l;
return 0;
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |