| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1330380 | randi_pav | Mobile (BOI12_mobile) | C++20 | 345 ms | 95860 KiB |
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <deque>
using namespace std;
typedef long double ld;
struct Tower {
ld x, y;
};
// Find the point x where two towers are equidistant
ld intersect(Tower a, Tower b) {
return (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2.0 * (b.x - a.x));
}
ld get_dist(Tower t, ld x) {
return sqrtl((t.x - x) * (t.x - x) + t.y * t.y);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; ld l;
cin >> n >> l;
vector<Tower> input(n);
for(int i=0; i<n; ++i) cin >> input[i].x >> input[i].y;
// 1. Remove duplicate X coordinates (keep smallest |y|)
vector<Tower> towers;
for(auto &t : input) {
if(!towers.empty() && towers.back().x == t.x) {
if(abs(t.y) < abs(towers.back().y)) towers.back() = t;
} else towers.push_back(t);
}
// 2. Build the Lower Envelope using a Deque
deque<Tower> dq;
for(auto &t : towers) {
while(dq.size() >= 2) {
if(intersect(dq[dq.size()-2], dq.back()) >= intersect(dq.back(), t))
dq.pop_back();
else break;
}
dq.push_back(t);
}
// 3. Trim the Deque to the highway range [0, L]
// If the intersection of the first two towers is < 0, the first tower is useless
while(dq.size() >= 2 && intersect(dq[0], dq[1]) <= 0)
dq.pop_front();
// If the intersection of the last two is > L, the last tower is useless
while(dq.size() >= 2 && intersect(dq[dq.size()-2], dq.back()) >= l)
dq.pop_back();
// 4. Calculate Max Distance
ld max_d = 0;
// Check boundaries
max_d = max(max_d, get_dist(dq.front(), 0));
max_d = max(max_d, get_dist(dq.back(), l));
// Check all internal intersections
for(int i = 0; i < (int)dq.size() - 1; ++i) {
ld x_int = intersect(dq[i], dq[i+1]);
// We already trimmed, so x_int is guaranteed to be within [0, L]
max_d = max(max_d, get_dist(dq[i], x_int));
}
cout << fixed << setprecision(6) << (double)max_d << endl;
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... | ||||
