Submission #1334514

#TimeUsernameProblemLanguageResultExecution timeMemory
1334514killerzaluuAstronomer (BOI23_astronomer)C++20
59 / 100
2094 ms468 KiB
//
#ifndef __SIZEOF_INT128__
  #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
constexpr int maxn = 703;
using ld = double;
constexpr ld eps = 1e-6;
bool eqd(double a, double b){
    return abs(a-b) < eps || abs((a-b)/min(a,b)) < eps;
}
struct pkt
{
    using t = double;
    t x, y;
    pkt(t a, t b) : x(a), y(b) {}
    pkt() : x(0), y(0) {}
    friend t operator*(pkt a, pkt b){return a.x*b.y - b.x*a.y;}
    friend pkt operator*(pkt a, t b){return {a.x*b, a.y*b};}
    friend pkt operator/(pkt a, t b){return {a.x/b, a.y/b};}
    friend pkt operator+(pkt a, pkt b){return {a.x+b.x, a.y+b.y};}
    friend pkt operator-(pkt a, pkt b){return {a.x-b.x, a.y-b.y};}
    bool z(){return y < 0 || (y == 0 && x < 0);}
    friend bool operator<(pkt a, pkt b){
        if(a.z() != b.z())return a.z() < b.z();
        return a*b < 0;
    }
    friend bool operator==(pkt a, pkt b){return eqd(a.x, b.x) && eqd(a.y, b.y);}
    friend bool operator!=(pkt a, pkt b){return !eqd(a.x, b.x) || !eqd(a.y, b.y);}
    // friend bool operator==(pkt a, pkt b){return a.x == b.x && a.y == b.y;}
    // friend bool operator!=(pkt a, pkt b){return a.x != b.x || a.y != b.y;}
    friend t d(pkt a, pkt b){return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}
    friend t dk(pkt a, pkt b){return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);}
    friend ostream& operator<<(ostream& out, pkt f){return out << '('<<(f.x) << ',' << (f.y)<<')';}
};
const pkt O = pkt(0,0);
pkt ar[maxn];
int n, k, s, t;
bool da(ld r)
{
    // Timer timer;
    // cerr << r << "?\n";
    rep(i, 0, n)if(d(ar[i], O)*s <= r){
        if(k == 1)return 1;
        auto f = [i](pkt p){return s*d(O, p)+ t*d(ar[i],p);};
        vector <pair <pkt, pkt>> itv;
        rep(j, 0, n)if(i != j){
            pkt o((ar[j]+ar[i])/2), a(ar[j]-ar[i]);
            if(f(o) > 2*r)continue;
            swap(a.x, a.y); a.y = -a.y;
            ld p(-1e9), k(1e9);
            while(!eqd(p, k)){
                ld l((51*p+50*k)/101), r((50*p+51*k)/101), fl(f(o+a*l)), fr(f(o+a*r));
                if(fl < fr) k = r;
                else p = l;
            }
            if(f(o + a*p) > r)continue;
            pair <pkt, pkt> it;
            o = o + a*p;
            p = 0; k = 1e9;
            while(!eqd(p,k)){
                if(f(o + a*((p+k)/2)) < r)p = (p+k)/2;
                else k =(p+k)/2;
            }
            it.first = o + a*p;
            p = 0; k = 1e9;
            while(!eqd(p, k)){
                if(f(o - a*((p+k)/2)) < r)p = (p+k)/2;
                else k =(p+k)/2;
            }
            it.second = o - a*p;
            it.first = it.first - ar[i];
            it.second = it.second - ar[i];
            if((it.first) * (it.second) > 0)swap(it.first, it.second);
            itv.pb(it);
        }
        if(!sz(itv))continue;
        // if(sz(itv)+1 < k)continue;
        // cout << ar[i] << ": " << itv << '\n';
        vector <pair <pkt, bool>> ma;
        for(auto [l, r]: itv){
            ma.pb(l,0);
            ma.pb(r,1);
        }
        sort(all(ma));
        int S(0);
        pkt g(ma.begin()->first);
        for(auto [l, r]: itv)S += (l * g < 0 && !(l== g)) && (g * r < 0 || g == r);
        int m(S);
        // cout << S << ' ';
        for(auto [x, y]: ma){
            m = max(m, (S = S + (y?-1:1)));
            // cout << S << ' ';
        }
        // cout << '\n';
        if(m+1 >= k)return 1;
    }
    return 0;
}
std::int32_t main()
{
    cout << setprecision(8) << fixed;
    std::cout.tie(nullptr); //for luck
    std::cin.tie(nullptr); std::ios_base::sync_with_stdio(0);
    cin >> k >> n >> s >> t;
    rep(i, 0, n)cin >> ar[i].x >> ar[i].y;
    if(t <= s){
        sort(ar, ar+n, [](pkt a, pkt b){return d(O, a) < d(O,b);});
        cout << d(O, ar[k-1])*t << '\n';
        return 0;
    }
    sort(ar, ar+n, [](pkt a, pkt b){return d(O, a) < d(O,b);});
    ld p(eps), kk(t*d(O, ar[k-1]));
    if(da(sqrt(p*k)))kk = sqrt(p*k);
    else p = sqrt(p*k);
    while(!eqd(p,kk)){
        ld s((p+kk)/2);
        if(da(s))kk = s;
        else p = s;
        // break;
    }
    cout << p << '\n';
    return 0;
}
#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...