// https://oj.uz/problem/view/BOI12_mobile
#include <bits/stdc++.h>
using namespace std;
#define forint(i, from, toinc) for (int i = from; i <= toinc; ++i)
void fio()
{
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef USEFILE
freopen("mobile.in", "r", stdin);
freopen("mobile.out", "w", stdout);
#endif
}
/*
some observations:
if we have 2 towers with the same x, (x, y1) and (x, y2),
we only need to keep the one with the smallest abs y value,
let's say |y1| <= |y2|, then we can safely forget (x, y2), because for any
point on the x axis, it will always be closer (<=) to (x, y1) than to (x, y2).
now we kind of cut the x axis into segments, enclosed by distinct x values we see.
for points between (x1,0) and (x2,0), corresponding to two towers (x1,y1) and (x2,y2),
the points equidistant to the two towers (x=,0) is the one with the max
min distant to these two points, because moving left, we have a point
that is closer to (x1,y1), and therefore a smaller max distance, and same for
moving right.
this point could still be closer to some other towers out of the [x1,x2] segment,
but we don't need to worry about it, because this distance would still be greater
than the one produced by the next segment.
for two towers at (x1,y1) and (x2,y2), the equidistant point (x,0) to
these towers has a close form of
x = (x2+x1)/2 + (y2^2 - y1^2) / 2(x2-x1)
if x2 < x, then the min distance is
sqrt((x2-x1)^2 + y1^2)
else if x > x1, min distance is
sqrt((x2-x1)^2 + y2^2)
*/
struct Point {
int x,y;
};
int tcnt; // tower count
vector<Point> towers;
int len; // all points on (0,0) to (len,0) to the towers
void debug()
{
cerr << "highway from (0,0) to (" << len << ",0)" << endl;
cerr << tcnt << " towers:";
forint(i, 0, tcnt-1) {
cerr << " " << towers[i].x << "," << towers[i].y;
}
cerr << endl;
}
void rdata()
{
cin >> tcnt >> len;
int lastx, lasty;
cin >> lastx >> lasty;
forint(i, 1, tcnt-1) {
int x, y;
cin >> x >> y;
if (x != lastx) {
towers.push_back({lastx, lasty});
lastx = x;
lasty = y;
} else if (abs(y) < abs(lasty)) {
lasty = y;
}
if (i == tcnt-1) {
towers.push_back({lastx, lasty});
}
}
tcnt = (int)towers.size();
}
double calc_maxd(int i1, int i2)
{
double x1 = towers[i1].x;
double y1 = towers[i1].y;
double x2 = towers[i2].x;
double y2 = towers[i2].y;
double y12 = y1*y1;
double y22 = y2*y2;
double dx2 = (x2-x1)*(x2-x1);
double x = (x2+x1) + (y22 - y12) / (x2-x1);
x /= 2;
double d2; // d*d
if (x < x1) {
d2 = dx2 + y22;
} else if (x > x2) {
d2 = dx2 + y12;
} else {
d2 = y22 + (x2-x)*(x2-x);
}
return sqrt(d2);
}
int main()
{
fio();
rdata();
#ifdef DEBUG
debug();
#endif
double minmaxd = DBL_MAX;
forint(i, 0, tcnt-2) {
minmaxd = min(minmaxd, calc_maxd(i, i+1));
}
cout << fixed << setprecision(3) << minmaxd << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
2220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
2144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
8564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
8664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
13264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
108 ms |
10284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
101 ms |
13420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
11932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
13580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
151 ms |
13576 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
136 ms |
16836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
189 ms |
16852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
