QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#961130#8266. AstronomerWansur0 65ms4224kbC++234.6kb2025-04-01 23:30:202025-04-01 23:30:21

Judging History

This is the latest submission verdict.

  • [2025-04-01 23:30:21]
  • Judged
  • Verdict: 0
  • Time: 65ms
  • Memory: 4224kb
  • [2025-04-01 23:30:20]
  • Submitted

answer

#include <bits/stdc++.h>
using ll = long long;
// const int N = ;

struct vector2d {
    double x, y;
    double angle() const {
        return atan2(y, x);
    }
    double dist() const {
        return sqrt(x * x + y * y);
    }
    auto &operator+=(const vector2d &v) {
        return x += v.x, y += v.y, *this;
    }
    auto &operator-=(const vector2d &v) {
        return x -= v.x, y -= v.y, *this;
    }
    friend auto operator-(vector2d a, const vector2d &b) {
        return a -= b;
    }
    friend auto operator+(vector2d a, const vector2d &b) {
        return a += b;
    }
    friend auto operator*(const vector2d &a, double b) {
        return vector2d{a.x * b, a.y * b};
    }
    friend std::ostream &operator<<(std::ostream &os, const vector2d &v) {
        return os << "(" << v.x << ", " << v.y << ")";
    }
};

struct line {
    double x, y;
    vector2d v;
};
line perpendicular_bisector(vector2d a, vector2d b) {
    return line{(a.x + b.x) / 2, (a.y + b.y) / 2, vector2d{a.y - b.y, b.x - a.x}};
}

auto pi = std::acos(-1.0);

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int k, n;
    double s, t;
    std::cin >> n >> k;
    s = 0, t = 1;
    std::vector<vector2d> a(n);

    for (auto &[x, y] : a)
        std::cin >> x >> y;

    std::shuffle(a.begin(), a.end(), std::mt19937());

    if (s >= t) {
        std::sort(a.begin(), a.end(), [&](auto a, auto b) {
            return a.dist() < b.dist();
        });
        std::cout << std::fixed << std::setprecision(10) << t *a[k - 1].dist() << '\n';
        return 0;
    }

    double ans = 1.5e18;

    for (int i = 0; i < n; i++) {
        if (k == 1) {
            ans = std::min(ans, s * a[i].dist());
            continue;
        }

        auto check = [&](double lim) {
            std::vector<std::pair<double, int>> ve;

            for (int j = 0; j < n; j++) {
                if (i == j)
                    continue;

                auto pb = perpendicular_bisector(a[i], a[j]);
                auto calc = [&](auto d) {
                    auto p = vector2d{pb.x, pb.y} + pb.v *d;
                    return s * p.dist() + t * (p - a[i]).dist();
                };
                double l = -1e9, r = 1e9;

                for (int t = 100; t; t--) {
                    double ml = l + (r - l) / 3, mr = r - (r - l) / 3;

                    if (calc(ml) < calc(mr))
                        r = mr;
                    else
                        l = ml;
                }

                if (calc(l) > lim)
                    continue;

                double ll = -1e9, lr = l;

                for (int t = 100; t; t--) {
                    double mid = (ll + lr) / 2;

                    if (calc(mid) < lim)
                        lr = mid;
                    else
                        ll = mid;
                }

                double rl = l, rr = 1e9;

                for (int t = 100; t; t--) {
                    double mid = (rl + rr) / 2;

                    if (calc(mid) < lim)
                        rl = mid;
                    else
                        rr = mid;
                }

                // std::cerr << (vector2d{pb.x, pb.y} + pb.v * ll) << ' ' << calc(ll) << ' ' << (vector2d{pb.x, pb.y} + pb.v * rl) << ' ' << calc(rl) << '\n';
                auto al = (vector2d{pb.x, pb.y} + pb.v * ll - a[i]).angle() + pi;
                auto ar = (vector2d{pb.x, pb.y} + pb.v * rl - a[i]).angle() + pi;

                if (al > ar)
                    std::swap(al, ar);

                if (ar - al > pi)
                    ve.emplace_back(ar, 1), ve.emplace_back(al + 2 * pi, -1);
                else
                    ve.emplace_back(al, 1), ve.emplace_back(ar, -1), ve.emplace_back(al + 2 * pi, 1), ve.emplace_back(ar + 2 * pi,
                            -1);
            }

            std::sort(ve.begin(), ve.end());
            int cur = 0;

            for (auto [x, y] : ve) {
                cur += y;

                if (cur >= k - 1)
                    return 1;
            }

            return 0;
        };
        double l = 0, r = ans;

        if (!check(r))
            continue;

        for (int t = 100; t; t--) {
            double mid = (l + r) / 2;

            if (check(mid))
                r = mid;
            else
                l = mid;
        }

        ans = std::min(ans, r);
        std::cerr << i << '\n';
    }

    std::cout << std::fixed << std::setprecision(10) << ans * ans * acos(-1) << '\n';



}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 4224kb

input:

5 50 100 10
83800992 -886133390
419292091 -739946592
23316601 -533703422
728805984 890308742
-66894195 66628784
154560403 -595148422
-827958439 928301296
849961738 946067907
310878751 -114000318
871656204 66733904
-791356839 125420374
-838471381 157736324
-911519472 -679917398
816843257 -363318953
-...

output:

7068583470577033914006087004170747904.0000000000

result:

wrong answer 1st numbers differ - expected: '4930145422.6525173', found: '7068583470577033914006087004170747904.0000000', error = '1433747458665021241458425856.0000000'

Subtask #2:

score: 0
Wrong Answer

Test #14:

score: 0
Wrong Answer
time: 65ms
memory: 4096kb

input:

50 50 0 100
-636373727 151906670
-436420422 -967929931
-946894101 -648810265
-318412226 -368156635
608567780 -787997497
40618170 966479708
-451370311 -406325088
830840722 -678655131
-89071166 -21371001
60891837 -615893965
785687617 -623669416
-513873386 -653229486
-555272924 350850129
-901712781 -32...

output:

5194980760581571584.0000000000

result:

wrong answer 1st numbers differ - expected: '128592913281.7085724', found: '5194980760581571584.0000000', error = '40398654.1669525'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #2:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Wrong Answer

Test #214:

score: 0
Wrong Answer
time: 0ms
memory: 4224kb

input:

5 50 100 10
460309761 -799742665
-100987677 761175444
-361900447 -449675625
-631196407 -1559607
-721861391 643436364
-122962913 5884730
295248578 491223378
986298998 468191512
-169039995 374919122
-46710929 402201182
-943494268 -547915393
521170382 929707215
355890998 688700401
-264192618 -469266213...

output:

7068583470577033914006087004170747904.0000000000

result:

wrong answer 1st numbers differ - expected: '3882365967.1217990', found: '7068583470577033914006087004170747904.0000000', error = '1820689633702240855202463744.0000000'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%