| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 683997 | as111 | Mobile (BOI12_mobile) | C++14 | 0 ms | 0 KiB |
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 <iostream>
#include <vector>
#include <set>
#define ll long long
#define MAXN 1000000
using namespace std;
int N, L;
vector<pair<ll, ll>> stns;
ll lt[MAXN + 5]; // point to the left
ll frac[MAXN + 5][2]; // point hypotenuse equals to station to the left, num and den
ll reach[MAXN + 5][2];
bool comp(int a, int b) {
ll ax = stns[a].first;
ll bx = stns[b].first;
if (frac[b][0] * frac[a][1] > frac[b][1] * (frac[a][0]+(bx-ax)*frac[a][1])) { // right point reaches further to the left than left does, delete left
return true;
}
}
void dist(int a, int b) {
ll ax = stns[a].first;
ll ay = stns[a].second;
ll bx = stns[b].first;
ll by = stns[b].second;
frac[b][0] = (ay * ay) + (bx - ax) * (bx - ax) - (by * by);
frac[b][1] = 2 * (bx - ax);
if (bx * frac[b][1] < frac[b][0]) frac[b][0] = 0; // point reaches to the left of 0, reset to 0
}
int main() {
cin >> N >> L;
stns.push_back({ -2000000001, -1000000001 });
for (int i = 0; i < N; i++) {
int x, y; cin >> x >> y;
if (stns.back().first == x) { // another with same x value
if (abs(stns.back().first) < abs(x)) continue;
else { // this one is closer, remove other of same x value
stns.pop_back();
stns.push_back({ x, y });
}
}
else {
stns.push_back({ x, y });
}
}
for (int i = 1; i <= N; i++) {
dist(i-1, i);
}
lt[1] = -1;
for (int i = 2; i <= N; i++) {
int prev = i - 1;
while (prev != -1) {
if (comp(i, prev)) {
prev = lt[prev];
}
else {
lt[i] = prev;
break;
}
}
if (prev == -1) lt[i] = -1; // leftmost point
}
double ans = 0;
for (int i = N; i >= 1; i = lt[i]) {
double hyp = sqrt(pow((double)frac[i][0] / (double)frac[i][1], 2) + pow(stns[i].second, 2));
ans = max(ans, hyp);
}
cout << ans;
}