Submission #1267165

#TimeUsernameProblemLanguageResultExecution timeMemory
1267165goppamachMobile (BOI12_mobile)C++20
0 / 100
1096 ms80960 KiB
// #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; #define el "\n" #define pii pair<int, int> #define pll pair<ll, ll> #define fi first #define se second #define sqr(x) ((x) * (x)) #define FOR(i, l, r) for (int i = l; i <= (r); i++) #define FOD(i, l, r) for (int i = l; i >= (r); i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((int)(x).size()) #define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); using db = long double; using ll = long long; using ull = unsigned long long; using vi = vector<int>; using vll = vector<ll>; using vpii = vector<pii>; using vpll = vector<pll>; using vvi = vector<vi>; using vvll = vector<vll>; using vbool = vector<bool>; using vvbool = vector<vbool>; template<class T> inline bool chmax(T &a, T const &b) { return (a < b ? (a = b, true) : false); } template<class T> inline bool chmin(T &a, T const &b) { return (a > b ? (a = b, true) : false); } // #define DEBUG #ifdef DEBUG #include "D:\cpp\debug.h" #else #define debug(...) #define debug_arr(...) #endif mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); constexpr int N = 1E6 + 5; constexpr db MAX = 1E9; constexpr db EPS = 1E-10; constexpr int PRECISION = 10; struct Point { db x, y; Point() = default; Point(db x, db y): x(x), y(y) {} }; struct Interval { db start, end; Interval(db start, db end): start(start), end(end) {} friend bool operator<(Interval const &a, Interval const &b) { return a.start < b.start || (a.start == b.start && a.end < b.end); } }; Point points[N]; int n, L; bool check(db r) { vector<Interval> intervals; FOR(i, 1, n) { if (r - points[i].y < EPS) return false; db d = sqrtl(sqr(r) - sqr(points[i].y)); intervals.emplace_back(points[i].x - d, points[i].x + d); } sort(all(intervals)); Interval merged = {0, 0}; bool started = false; for (auto const &interval : intervals) { if (!started) { merged = interval; started = true; } else if (merged.end < interval.start) { // there are disjoint intervals return false; } else { chmax(merged.end, interval.end); } } return merged.start <= 0 && merged.end >= L; } void solve() { cin >> n >> L; FOR(i, 1, n) { db x, y; cin >> x >> y; points[i] = {x, y}; } db l = 0, r = MAX, res = MAX; while (r - l >= EPS) { db m = (l + r) / 2; if (check(m)) { res = m; r = m; } else { l = m; } } cout << fixed << setprecision(PRECISION) << res << el; } int main() { fast_io #define LOCAL #ifndef LOCAL #define PROBLEM "" freopen(PROBLEM ".INP", "r", stdin); freopen(PROBLEM ".OUT", "w", stdout); #endif int t = 1; // cin >> t; while (t--) solve(); }
#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...