Submission #1333923

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

struct Point {
    double x, y;
};

double dist(const Point &a, const Point &b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
}

// Circumcircle of 3 points
pair<Point, double> circumcircle(const Point &A, const Point &B, const Point &C) {
    double a = B.x - A.x, b = B.y - A.y;
    double c = C.x - A.x, d = C.y - A.y;
    double e = a*(A.x+B.x) + b*(A.y+B.y);
    double f = c*(A.x+C.x) + d*(A.y+C.y);
    double det = 2*(a*(d)-b*(c));
    if(fabs(det) < 1e-12) return {{0,0}, 1e18}; // degenerate
    double cx = (d*e - b*f)/det;
    double cy = (-c*e + a*f)/det;
    Point center = {cx, cy};
    double radius = dist(center, A);
    return {center, radius};
}

// Circle from 2 points (two possible circles with given radius)
vector<pair<Point,double>> circlesFromPair(const Point &A, const Point &B) {
    vector<pair<Point,double>> res;
    double d = dist(A,B);
    Point mid = {(A.x+B.x)/2, (A.y+B.y)/2};
    double r = d/2;
    double dx = (B.y - A.y)/d * r;
    double dy = (A.x - B.x)/d * r;
    // Two possible centers
    res.push_back({{mid.x + dx, mid.y + dy}, r});
    res.push_back({{mid.x - dx, mid.y - dy}, r});
    return res;
}

int main() {
    int k, n;
    double s, f;
    cin >> k >> n >> s >> f;
    vector<Point> stars(n);
    for(int i=0;i<n;i++) cin >> stars[i].x >> stars[i].y;

    double best = 1e18;
    const double eps = 1e-9;

    // Single stars
    for(int i=0;i<n;i++){
        Point c = stars[i];
        int cnt = 0;
        for(int j=0;j<n;j++)
            if(dist(c, stars[j]) <= eps) cnt++;
        if(cnt >= k){
            double cost = f*0 + s*dist({0,0}, c);
            best = min(best, cost);
        }
    }

    // Pairs
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            auto circles = circlesFromPair(stars[i], stars[j]);
            for(auto &[c, r] : circles){
                int cnt = 0;
                for(int t=0;t<n;t++)
                    if(dist(c, stars[t]) <= r + eps) cnt++;
                if(cnt >= k){
                    double cost = f*r + s*dist({0,0}, c);
                    best = min(best, cost);
                }
            }
        }
    }

    // Triplets
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            for(int t=j+1;t<n;t++){
                auto [c, r] = circumcircle(stars[i], stars[j], stars[t]);
                if(r > 1e16) continue; // degenerate
                int cnt = 0;
                for(int p=0;p<n;p++)
                    if(dist(c, stars[p]) <= r + eps) cnt++;
                if(cnt >= k){
                    double cost = f*r + s*dist({0,0}, c);
                    best = min(best, cost);
                }
            }
        }
    }

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