Submission #1314125

#TimeUsernameProblemLanguageResultExecution timeMemory
1314125tkhoi13Mobile (BOI12_mobile)C++20
8 / 100
510 ms79432 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define db double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define szx(x) ((int)(x).size())
#define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i)
#define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define endl '\n'
#define inf 1000000007
#define mod 1000000007
// #define mod 998244353

using namespace std;
using namespace __gnu_pbds;

void setIO() {
    ios::sync_with_stdio(0);
    cin.tie(0);
}
void openFile(string filename = "") {
    if (!filename.empty())
        if (ifstream(filename + ".in")) {
            freopen((filename + ".in").c_str(), "r", stdin);
            freopen((filename + ".out").c_str(), "w", stdout);
        }
}
ll binpow(ll a, ll b, int m = mod) {
    ll res = 1;
    a %= m;
    while (b) {
        if (b & 1) res = (a * res) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res;
}
const int FMAX = 2e5 + 5;
ll fact[FMAX], invf[FMAX];
void process() {
    fact[1] = fact[0] = invf[1] = invf[0] = 1;
    FOR(i, 2, FMAX - 1) fact[i] = (fact[i - 1] * i) % mod;
    invf[FMAX - 1] = binpow(fact[FMAX - 1], mod - 2, mod);
    ROF(i, FMAX - 1, 1) invf[i - 1] = invf[i] * i % mod;
}
ll comb(int a, int b) {
    b = min(b, a - b);
    if (a < 0 || b < 0) return 0;
    return fact[a] * (invf[b] * invf[a - b] % mod) % mod;
}
const int PMAX = 1e6 + 5;
bool prime[PMAX + 1];
void sieve() {
    fill(prime, prime + PMAX + 1, 1);
    prime[0] = prime[1] = 0;
    for (int i = 2; i * i <= PMAX; i++) {
        if (prime[i] == 0) continue;
        prime[i] = 1;
        for (ll j = i * i; j <= PMAX; j += i) prime[j] = 0;
    }
}
struct DSU {
    vector<int> comp;
    ll ans = 0;
    DSU(int n) { comp.assign(n + 5, -1); }

    int find(int v) { return comp[v] < 0 ? v : comp[v] = find(comp[v]); }

    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;

        if (comp[u] > comp[v]) swap(u, v);
        comp[u] += comp[v];
        comp[v] = u;
    }

    int getsz(int v) { return -comp[find(v)]; }
    bool same(int u, int v) { return find(u) == find(v); }
};

struct Point {
    db x, y;
    Point(db x, db y) : x(x), y(y) {}
    Point() {};
};

struct Vector {
    ll x, y;
    Vector(Point A, Point B) {
        x = A.x - B.x;
        y = A.y - B.y;
    }
    Vector(ll x, ll y) : x(x), y(y) {};
    Vector PerpenVec() { return Vector(y, -x); }
};

struct Line {
    ll a, b;
    db c;

    Line(Vector v, Point A) {
        Vector PerpenVec = v.PerpenVec();
        a = PerpenVec.x;
        b = PerpenVec.y;
        c = -(a * A.x + b * A.y);
    }
};

Line bisectorLine(Point A, Point B) {
    Point midPoint = Point((A.x + B.x) / 2, (A.y + B.y) / 2);
    Vector v = Vector(A, B).PerpenVec();

    return Line(v, midPoint);
}

Point intersec(Line A, Line B) {
    ll delta = A.b * B.a - A.a * B.b;
    if (delta == 0) return Point(-inf, -inf);

    return Point(1.0 * (A.c * B.b - A.b * B.c) / delta, -1.0 * (A.c * B.a - A.a * B.c) / delta);
}

db distance(Point A, Point B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
const int MAX = 1e6 + 5;
int n, l;
Point stations[MAX];
Line Ox = Line(Vector(1, 0), Point(0, 0));

map<int, int> mp;

void solve() {
    stack<Point> st;
    n = szx(mp);
    int cnt = 0;
    for (pii p : mp) stations[cnt].x = p.fi, stations[cnt].y = p.se, cnt++;
    REP(i, n) {
        while (szx(st) >= 2) {
            Point B = st.top();
            st.pop();
            Point A = st.top();

            Line b1 = bisectorLine(A, B), b2 = bisectorLine(B, stations[i]);

            if (intersec(b1, Ox).x < intersec(b2, Ox).x) {
                st.push(B);
                break;
            }
        }

        st.push(stations[i]);
    }

    db ans = -1e18;
    db mn1 = 1e18, mn2 = 1e18;
    REP(i, n)
    mn1 = min(mn1, distance(Point(0, 0), stations[i])),
    mn2 = min(mn2, distance(Point(l, 0), stations[i]));

    ans = max(mn1, mn2);

    while (szx(st) >= 2) {
        Point A = st.top();
        st.pop();
        Point B = st.top();
        Point C = intersec(bisectorLine(A, B), Ox);

        db d = distance(C, A);
        if (C.x >= 0 && C.x <= l) ans = max(ans, d);
    }

    cout << ans;
}

void input() {
    cin >> n >> l;
    REP(i, n) {
        int x, y;
        cin >> x >> y;
        if (!mp.count(x) || abs(mp[x]) > abs(y)) mp[x] = y;
    }
}

void preprocess() {}

int main() {
    setIO();
    openFile("main");
    int t = 1;
    // cin >> t;
    preprocess();
    while (t--) {
        input();
        solve();
    }
}

Compilation message (stderr)

mobile.cpp: In function 'void openFile(std::string)':
mobile.cpp:32:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |             freopen((filename + ".in").c_str(), "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobile.cpp:33:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |             freopen((filename + ".out").c_str(), "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...