Submission #1229666

#TimeUsernameProblemLanguageResultExecution timeMemory
1229666atillamaMobile (BOI12_mobile)C++20
0 / 100
1097 ms65224 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset; #define int long long #define double long double #define pb push_back #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cout << #x << " = " << x << '\n'; #define vdebug(a) cout << #a << " = "; for(auto x : a) cout << x << " "; cout << '\n'; const double eps = 1e-9; const int mod = 1e9 + 7; const int N = 2e5 + 5; const int INF = 1e18; signed main(){ fastio; int n, l; cin >> n >> l; vector<pair<int, int>> v; double lo = 0; for(int i = 1; i <= n; i++){ int x, y; cin >> x >> y; v.pb({x, y}); lo = max(lo, (double)y); } double best = INF; double hi = l; while(hi - lo > 1e-4){ double mid = (hi + lo) / 2.0; vector<pair<double, double>> lr; // l, r for(int i = 0; i < n; i++){ int x = v[i].first; int y = v[i].second; // a*a + b*b = c*c // a*a + y*y = mid*mid double a = sqrtl(mid * mid - y * y); lr.pb({x - a, x + a}); } sort(lr.begin(), lr.end()); bool b = true; if(lr[0].first > 0){ b = false; } double mxr = lr[0].second; for(int i = 1; i < lr.size(); i++){ mxr = max(mxr, lr[i - 1].second); if(lr[i].first > mxr){ b = false; break; } } if(b){ best = mid; hi = mid; }else{ lo = mid; } } cout << best << '\n'; } /* freopen("x.in", "r", stdin); freopen("x.out", "w", stdout); */ //atilla
#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...