| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1286666 | samarthkulkarni | Mobile (BOI12_mobile) | C++20 | 0 ms | 0 KiB |
void solution() {
ll N;
ld L;
cin >> N >> L;
vector<pair<ld, ld>> a(N);
for (int i = 0; i < N; i++) {
ld x, y;
cin >> x >> y;
a[i] = {x, y};
}
// This function now correctly returns 'true' if the highway is FULLY COVERED.
auto isCovered = [&](ld d) {
vector<pair<ld, ld>> intervals;
ld d_squared = d * d;
// --- BUG FIX #1: Correctly handle stations that can't reach ---
for (int i = 0; i < N; i++) {
if (d < abs(a[i].ss)) {
continue; // Skip stations that are too far from the highway.
}
ld radius_on_highway = sqrt(d_squared - a[i].ss * a[i].ss);
ld p = max((ld)0.0, a[i].ff - radius_on_highway);
ld q = min(L, a[i].ff + radius_on_highway);
if (p <= q) {
intervals.push_back({p, q});
}
}
if (intervals.empty()) {
return L <= 1e-9; // Covered only if highway length is effectively zero.
}
sort(all(intervals));
// --- BUG FIX #2: Robust greedy interval merging logic ---
ld coverage_end = 0.0;
if (intervals[0].ff > 1e-9) {
return false; // Gap at the very start of the highway.
}
ld max_reach_this_step = 0.0;
int i = 0;
while (coverage_end < L) {
// Find the furthest reachable point from all intervals that start within our current coverage.
while (i < intervals.size() && intervals[i].ff <= coverage_end + 1e-9) {
max_reach_this_step = max(max_reach_this_step, intervals[i].ss);
i++;
}
// If we couldn't extend our coverage, it means there's a gap.
if (max_reach_this_step <= coverage_end) {
return false;
}
coverage_end = max_reach_this_step;
}
return true; // If the loop completes, the highway is fully covered.
};
// --- BUG FIX #3: Correct binary search for the MINIMUM passing value ---
ld p = 0, q = 2e9; // A safe upper bound
// We run for a fixed number of iterations to guarantee precision.
for(int i = 0; i < 100; ++i) {
ld mid = p + (q - p) / 2;
if (isCovered(mid)) {
// 'mid' works. Let's try for an even SMALLER radius.
q = mid;
} else {
// 'mid' failed. We MUST use a LARGER radius.
p = mid;
}
}
// The answer is 'q', the smallest value for which isCovered(q) was true.
cout << fixed << setprecision(10) << q << endl;
}