Submission #1344474

#TimeUsernameProblemLanguageResultExecution timeMemory
1344474s3narasiAstronomer (BOI23_astronomer)C++20
0 / 100
23 ms452 KiB
#include <bits/stdc++.h>
using namespace std;

using ld = long double;
const ld PI = acosl(-1);
const ld EPS = 1e-12;

int k, n;
ld s, t;

vector<pair<ld, ld>> a;

ld dist(ld x, ld y) {
    return sqrtl(x*x + y*y);
}

bool feasible(ld r, ld D) {
    // Handle D = 0 separately
    if (D < EPS) {
        int cnt = 0;
        for (auto &[x, y] : a) {
            if (dist(x, y) <= r + EPS) cnt++;
        }
        return cnt >= k;
    }

    vector<pair<ld,int>> ev;

    for (auto &[x, y] : a) {
        ld d = dist(x, y);

        if (d > r + D + EPS) continue;

        if (d < EPS) {
            ev.emplace_back(-PI, +1);
            ev.emplace_back(PI, -1);
            continue;
        }

        ld theta = atan2l(y, x);

        ld val = (d*d + D*D - r*r) / (2*d*D);
        val = max((ld)-1, min((ld)1, val));

        ld alpha = acosl(val);

        ld L = theta - alpha;
        ld R = theta + alpha;

        // handle circular wrap
        if (L < -PI) {
            ev.emplace_back(L + 2*PI, +1);
            ev.emplace_back(PI, -1);
            ev.emplace_back(-PI, +1);
            ev.emplace_back(R, -1);
        } else if (R > PI) {
            ev.emplace_back(L, +1);
            ev.emplace_back(PI, -1);
            ev.emplace_back(-PI, +1);
            ev.emplace_back(R - 2*PI, -1);
        } else {
            ev.emplace_back(L, +1);
            ev.emplace_back(R, -1);
        }
    }

    sort(ev.begin(), ev.end(), [](auto &a, auto &b) {
        if (fabsl(a.first - b.first) > 1e-12)
            return a.first < b.first;
        return a.second > b.second; // +1 before -1
    });

    int cur = 0;
    for (auto &[ang, type] : ev) {
        cur += type;
        if (cur >= k) return true;
    }

    return false;
}

bool check(ld cost) {
    ld lo = 0, hi = 2e9;

    for (int it = 0; it < 40; it++) {
        ld r = (lo + hi) / 2;

        ld D;
        if (s == 0) D = 1e18;
        else D = (cost - t*r) / s;

        if (D < 0) {
            lo = r;
            continue;
        }

        if (feasible(r, D)) {
            hi = r;
        } else {
            lo = r;
        }
    }

    ld r = hi;
    ld D = (s == 0 ? 1e18 : (cost - t*r)/s);
    if (D < 0) return false;

    return feasible(r, D);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> k >> n >> s >> t;

    a.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    ld lo = 0, hi = 1e18;

    for (int it = 0; it < 60; it++) {
        ld mid = (lo + hi) / 2;
        if (check(mid)) hi = mid;
        else lo = mid;
    }

    cout << fixed << setprecision(10) << (double)hi << "\n";
}
#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...