Submission #34512166

---

Source Code Expand

#include <bits/extc++.h>
#include <atcoder/fenwicktree>

int main(){
    using namespace std;
    unsigned long N, K;
    cin >> N >> K;
    cout << fixed << setprecision(15);

    using real = double;
    const real pi_half{1.5707963267948966192313216916397514420985846996876};
    const real pi{3.1415926535897932384626433832795028841971693993751};
    const real pi_triple_half{4.7123889803846898576939650749192543262957540990627};
    const real pi_2{6.2831853071795864769252867665590057683943387987502};
    vector<tuple<real, long, long, long>> lines(N);
    for(auto&& [theta, A, B, C] : lines){
        cin >> A >> B >> C;
        if(C > 0){
            A *= -1;
            B *= -1;
            C *= -1;
        }
        const auto d{sqrt(A * A + B * B)};
        if(B > 0){
            if(-B < A && A < B){
                const auto cos_theta{A / d};
                theta = pi_half - asin(cos_theta);
            }else{
                const auto sin_theta{B / d};
                theta = A > 0 ? asin(sin_theta) : pi - asin(sin_theta);
            }
        }else{
            if(B < A && A < -B){
                const auto cos_theta{A / d};
                theta = pi_triple_half + asin(cos_theta);
            }else{
                const auto sin_theta{B / d};
                theta = A > 0 ? pi_2 + asin(sin_theta) : pi - asin(sin_theta);
            }
        }
    }
    sort(begin(lines), end(lines));

    auto check{[&K, &pi_2, &pi_half, &lines](const auto& r_sq){
        vector<tuple<real, unsigned long, unsigned long>> intersections;
        unsigned long line_idx{};
        for(const auto& [theta, A, B, C] : lines)if(0 <= copysign(1, fma(r_sq, A * A + B * B, -C * C))){
            const real phi{0 <= copysign(1, fma(r_sq, A * A + B * B, -2 * C * C)) ? pi_half - asin(sqrt(C * C / r_sq / (A * A + B * B))) : asin(sqrt(1 - C * C / r_sq / (A * A + B * B)))};
            const real angle_0{theta + phi <= pi_2 ? theta + phi : theta + phi - pi_2}, angle_1{theta - phi >= 0 ? theta - phi : theta - phi + pi_2};
            intersections.emplace_back(angle_0, angle_0 <= angle_1, line_idx);
            intersections.emplace_back(angle_1, angle_0 > angle_1, line_idx);
            ++line_idx;
        }
        sort(begin(intersections), end(intersections));

        vector<pair<unsigned long, unsigned long>> segments(size(intersections) / 2);
        unsigned long intersection_idx{};
        for(const auto& [agl, t, i] : intersections)(t ? segments[i].second : segments[i].first) = intersection_idx++;
        sort(begin(segments), end(segments));
        atcoder::fenwick_tree<unsigned long> binary_indexed_tree(size(intersections));
        unsigned long ans{};
        for(const auto [r, l] : segments){
            ans += binary_indexed_tree.sum(0, l);
            binary_indexed_tree.add(l, 1);
            binary_indexed_tree.add(r, ~0UL);
        }
        return ans < K;
    }};

    cout << fixed << setprecision(15);
    constexpr unsigned long nibutan_iter{18};
    if(check(1.0)){
        double L_sq{1}, R_sq{7984010000000}; // (N, K) = (2, 1), [(A, B, C)] = [(-1000, -999, 1000), (999, 998, 1000)] -> ans = √7984010000000
        for(unsigned long iter{}; iter < nibutan_iter; ++iter){
            const double M{sqrt(L_sq * R_sq)};
            (check(M) ? L_sq : R_sq) = M;
        }
        cout << sqrt(L_sq) << endl;
    }else{
        double L_sq{0}, R_sq{1};
        for(unsigned long iter{}; iter < nibutan_iter; ++iter){
            const double M{(L_sq + R_sq + 2 * sqrt(L_sq) * sqrt(R_sq)) / 4};
            (check(M) ? L_sq : R_sq) = M;
        }
        cout << sqrt(L_sq) << endl;
    }

    return 0;
}

Submission Info

Judge Result