Submission #1056931

#TimeUsernameProblemLanguageResultExecution timeMemory
1056931TimAniMobile (BOI12_mobile)C++17
50 / 100
1096 ms24160 KiB
// time-limit: 3000 #include <bits/stdc++.h> using namespace std; using ll = long long; const double eps = 1E-4; struct point { int x{}, y{}; }; void solve() { int n, L; cin >> n >> L; vector<point> p(n); for(int i = 0; i < n; i++) { cin >> p[i].x >> p[i].y; } auto intersection = [&](const point& A, double R) -> array<double, 2> { if(abs(A.y) > R) { return {1e18, -1e18}; } double D = 1.0 * R * R - 1.0 * A.y * A.y; // divided by 4 double x1 = A.x - sqrt(D); double x2 = A.x + sqrt(D); if(x2 < x1) swap(x1, x2); return {x1, x2}; }; auto good = [&](double R) { vector<array<double, 2>> segs(n); for(int i = 0; i < n; i++) { segs[i] = intersection(p[i], R); } sort(segs.begin(), segs.end()); int i = 0; double r = 0; while(i < n && r >= segs[i][0]) { r = max(r, segs[i][1]); i++; } return r >= L; }; double l = 0, r = 4e9; while(r - l > eps) { double R = (r + l) / 2; if(good(R)) { r = R; } else { l = R; } } cout << fixed << setprecision(-log10(eps)) << r << endl; } int main() { cin.tie(0)->sync_with_stdio(0); double T = 1; //cin >> T; while(T--) solve(); return 0; }
#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...