Submission #1334521

#TimeUsernameProblemLanguageResultExecution timeMemory
1334521killerzaluuAstronomer (BOI23_astronomer)C++20
0 / 100
406 ms480 KiB
#include <bits/stdc++.h>
using namespace std;

using ld = long double;
const ld eps = 1e-6;

struct pkt {
    ld x, y;
    pkt(ld a=0, ld b=0): x(a), y(b) {}
    friend pkt operator+(const pkt &a, const pkt &b){ return {a.x+b.x, a.y+b.y}; }
    friend pkt operator-(const pkt &a, const pkt &b){ return {a.x-b.x, a.y-b.y}; }
    friend pkt operator*(const pkt &a, ld b){ return {a.x*b, a.y*b}; }
    friend pkt operator/(const pkt &a, ld b){ return {a.x/b, a.y/b}; }
    friend ld operator*(const pkt &a, const pkt &b){ return a.x*b.y - a.y*b.x; } // cross product
    bool z() const { return y < 0 || (y == 0 && x < 0); }
    bool operator<(const pkt &b) const {
        if(z() != b.z()) return z() < b.z();
        return (*this)*b < 0;
    }
    bool operator==(const pkt &b) const { return abs(x-b.x)<eps && abs(y-b.y)<eps; }
};

inline ld d(const pkt &a, const pkt &b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }

int n, k, s, t;
pkt ar[703];

bool eqd(ld a, ld b){ return abs(a-b)<eps || abs((a-b)/min(a,b)) < eps; }

// Check if radius r can cover k stars
bool da(ld r){
    for(int i=0;i<n;i++){
        if(d(ar[i], {0,0})*s > r) continue;
        if(k==1) return true;

        vector<pair<pkt,pkt>> intervals;
        for(int j=0;j<n;j++){
            if(i==j) continue;

            pkt o = (ar[i]+ar[j])/2;
            pkt a = ar[j]-ar[i];

            if(s*d({0,0}, ar[j])+t*d(ar[i],ar[j]) > r) continue;

            // rotate 90 degrees
            swap(a.x, a.y); a.y = -a.y;

            ld p=-1e9, q=1e9;
            while(!eqd(p,q)){
                ld l=(51*p+50*q)/101;
                ld m=(p+q)/2;
                ld r1 = s*d({0,0}, o+a*l) + t*d(ar[i], o+a*l);
                ld r2 = s*d({0,0}, o+a*m) + t*d(ar[i], o+a*m);
                if(r1 < r2) q=m; else p=l;
            }

            pkt first = o + a*p;
            pkt second = o - a*p;
            first = first - ar[i];
            second = second - ar[i];
            if((first*second)>0) swap(first, second);
            intervals.push_back({first, second});
        }

        if(intervals.empty()) continue;

        vector<pair<pkt,bool>> events;
        for(auto &[l,r]: intervals){
            events.push_back({l,0});
            events.push_back({r,1});
        }
        sort(events.begin(), events.end());

        int S=0, M=0;
        for(auto &[p,flag]: events){
            if(flag) S--; else S++;
            M = max(M,S);
        }

        if(M+1 >= k) return true;
    }
    return false;
}

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

    cin >> k >> n >> s >> t;
    for(int i=0;i<n;i++) cin >> ar[i].x >> ar[i].y;

    sort(ar, ar+n, [](pkt a, pkt b){ return d(a,{0,0}) < d(b,{0,0}); });

    ld lo=0, hi=1e18;
    for(int it=0;it<100;it++){
        ld mid = (lo+hi)/2;
        if(da(mid)) hi = mid;
        else lo = mid;
    }

    cout << fixed << setprecision(12) << hi << "\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...