| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 683997 |
2023-01-19T23:17:48 Z |
as111 |
Mobile (BOI12_mobile) |
C++14 |
|
0 ms |
0 KB |
#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;
}
Compilation message
mobile.cpp: In function 'int main()':
mobile.cpp:63:21: error: 'pow' was not declared in this scope
63 | double hyp = sqrt(pow((double)frac[i][0] / (double)frac[i][1], 2) + pow(stns[i].second, 2));
| ^~~
mobile.cpp:63:16: error: 'sqrt' was not declared in this scope
63 | double hyp = sqrt(pow((double)frac[i][0] / (double)frac[i][1], 2) + pow(stns[i].second, 2));
| ^~~~
mobile.cpp: In function 'bool comp(int, int)':
mobile.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
18 | }
| ^
