제출 #1334454

#제출 시각아이디문제언어결과실행 시간메모리
1334454killerzaluuAstronomer (BOI23_astronomer)C++20
0 / 100
3 ms348 KiB
#include <bits/stdc++.h>
using namespace std;

struct Point {
    long double x, y;
};

// squared distance
long double dist2(const Point &a, const Point &b) {
    long double dx = a.x - b.x;
    long double dy = a.y - b.y;
    return dx*dx + dy*dy;
}

// distance
long double dist(const Point &a, const Point &b) {
    return sqrt(dist2(a,b));
}

// check how many points are inside circle
long long count_inside(const Point &c, long double r, const vector<Point> &stars) {
    long long cnt = 0;
    long double rr = r*r;
    for(auto &p : stars){
        if(dist2(p, c) <= rr + 1e-12) cnt++;
    }
    return cnt;
}

// circumcircle of 3 points
bool circumcircle(const Point &A, const Point &B, const Point &C, Point &center, long double &r) {
    long double ax = A.x, ay = A.y;
    long double bx = B.x, by = B.y;
    long double cx = C.x, cy = C.y;

    long double d = 2*(ax*(by-cy) + bx*(cy-ay) + cx*(ay-by));
    if(fabsl(d) < 1e-12) return false; // points collinear

    long double ux = ((ax*ax + ay*ay)*(by - cy) + (bx*bx + by*by)*(cy - ay) + (cx*cx + cy*cy)*(ay - by))/d;
    long double uy = ((ax*ax + ay*ay)*(cx - bx) + (bx*bx + by*by)*(ax - cx) + (cx*cx + cy*cy)*(bx - ax))/d;

    center = {ux, uy};
    r = dist(center, A);
    return true;
}

int main() {
    long long n, k;
    long double s, t;
    cin >> k >> n >> s >> t;

    vector<Point> stars(n);
    for(long long i=0;i<n;i++){
        cin >> stars[i].x >> stars[i].y;
    }

    long double ans = 1e30;

    // k==1 case: radius 0 at any star
    if(k == 1){
        for(auto &p : stars){
            ans = min(ans, (long double)0.0); // radius 0
        }
    }

    // check all pairs
    for(long long i=0;i<n-1;i++){
        for(long long j=i+1;j<n;j++){
            Point c = {(stars[i].x + stars[j].x)/2, (stars[i].y + stars[j].y)/2};
            long double r = dist(stars[i], stars[j])/2;
            if(count_inside(c, r, stars) >= k)
                ans = min(ans, r);
        }
    }

    // check all triples
    for(long long i=0;i<n-2;i++){
        for(long long j=i+1;j<n-1;j++){
            for(long long l=j+1;l<n;l++){
                Point c;
                long double r;
                if(!circumcircle(stars[i], stars[j], stars[l], c, r)) continue;
                if(count_inside(c, r, stars) >= k)
                    ans = min(ans, r);
            }
        }
    }

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