Submission #1267168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267168		goppamach	Mobile (BOI12_mobile)	C++20	0 / 100	1098 ms	48176 KiB

mobile

// #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 double MAX = 2E9;
constexpr double EPS = 1E-6;
constexpr int PRECISION = 6;

struct Point {
    ll x, y;
    Point() = default;
    Point(ll x, ll y): x(x), y(y) {}
};

Point points[N];
int n, L;

bool check(double r) {
    vector<pair<double, double>> intervals;
    FOR(i, 1, n) {
        double delta = sqrt(sqr(r) - sqr(points[i].y));
        intervals.emplace_back(points[i].x - delta, points[i].x + delta);
    }
    sort(all(intervals));

    pair<double, double> merged = {0, 0};
    bool started = false;
    for (auto const &iv : intervals) {
        if (!started) {
            merged = iv;
            started = true;
        } else if (merged.se < iv.fi) { // there are disjoint intervals
            return false;
        } else {
            chmax(merged.se, iv.se);
        }
    }

    return merged.fi <= 0 && merged.se >= L;
}

void solve() {
    cin >> n >> L;

    FOR(i, 1, n) {
        ll x, y;
        cin >> x >> y;
        points[i] = {x, y};
    }

    double l = 1, r = MAX, res = MAX;
    while (r - l > EPS) {
        double 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();
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5