제출 #1334450

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

long double distance(pair<long double, long double> x, pair<long double, long double> y) {
    long double dx = x.first - y.first;
    long double dy = x.second - y.second;
    return sqrt(dx*dx + dy*dy);
}

// Count how many points in z are inside circle centered at x with radius r
long long check(pair<long double, long double> x, long double r, const vector<pair<long double, long double>>& z) {
    long long cnt = 0;
    long double rr = r*r; // compare squared distances
    for(auto &p : z){
        long double dx = p.first - x.first;
        long double dy = p.second - x.second;
        if(dx*dx + dy*dy <= rr + 1e-9) cnt++;
    }
    return cnt;
}

// Compute circumcircle of 3 points
bool circumcircle(pair<long double,long double> A,
                  pair<long double,long double> B,
                  pair<long double,long double> C,
                  pair<long double,long double> &center,
                  long double &r)
{
    long double ax=A.first, ay=A.second;
    long double bx=B.first, by=B.second;
    long double cx=C.first, cy=C.second;

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

    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 = distance(center, A);

    return true;
}

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

    vector<pair<long double,long double>> a;

    for(i=1; i<=n; i++) {
        long double b,c; 
        cin >> b >> c;
        a.push_back({b,c});
    }

    long double ans = 1e30; // large initial value

    // Pair case: circle diameter through two points
    for(i=0; i<n-1; i++){
        for(j=i+1; j<n; j++){
            pair<long double,long double> c;
            c.first  = (a[i].first + a[j].first)/2;
            c.second = (a[i].second + a[j].second)/2;
            long double r = distance(a[i], a[j])/2;
            if(check(c, r, a) >= k) {
                ans = min(ans, r);
            }
        }
    }

    // Triple case: circle through 3 points
    for(i=0; i<n-2; i++){
        for(j=i+1; j<n-1; j++){
            for(l=j+1; l<n; l++){
                pair<long double,long double> c;
                long double r;
                if(!circumcircle(a[i], a[j], a[l], c, r)) continue;
                if(check(c, r, a) >= k){
                    ans = min(ans, r);
                }
            }
        }
    }

    cout << fixed << setprecision(12) << ans * t << endl;
}
#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...