제출 #88096

#제출 시각아이디문제언어결과실행 시간메모리
88096JustInCaseMobile (BOI12_mobile)C++17
8 / 100
1084 ms74804 KiB
#include <bits/stdc++.h> const int32_t MAX_N = 1e6; const double EPS = 1e-6; int32_t n, l; std::pair< int32_t, int32_t > points[MAX_N + 5]; bool Check(long double r) { std::vector< std::pair< long double, bool > > events(2 * n); for(int32_t i = 0; i < n; i++) { if(r * r < (int64_t) points[i].second * points[i].second) { events[2 * i] = { -2.0, 0 }; events[2 * i + 1] = { -1.0, 1 }; continue; } long double x1 = points[i].first - sqrt(r * r - (int64_t) points[i].second * points[i].second); long double x2 = points[i].first + sqrt(r * r - (int64_t) points[i].second * points[i].second); events[2 * i] = { x1, 0 }; events[2 * i + 1] = { x2, 1 }; } std::sort(events.begin(), events.end()); if(r == 5.0) { for(int32_t i = 0; i < 2 * n; i++) { std::cout << " " << events[i].first << " " << events[i].second << '\n'; } } int32_t currCnt = 0; for(int32_t i = 0; i < 2 * n; i++) { if(events[i].first > 0 && currCnt == 0) { return false; } if(events[i].first > l) { break; } if(events[i].second == 0) { currCnt++; } else { currCnt--; } if(!(events[i].first < 0.0) && currCnt == 0) { return false; } } return true; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::cin >> n >> l; for(int32_t i = 0; i < n; i++) { std::cin >> points[i].first >> points[i].second; } int64_t low = 1, high = 1e16; long double ans; while(low <= high) { int64_t mid = (low + high) / 2; if(Check(mid / 10000.0)) { ans = mid / 10000.0; high = mid - 1; } else { low = mid + 1; } } std::cout << std::fixed << std::setprecision(7); std::cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...