제출 #1344343

#제출 시각아이디문제언어결과실행 시간메모리
1344343s3narasiAstronomer (BOI23_astronomer)C++20
0 / 100
17 ms1472 KiB
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long double ld;

struct Point {
    ld x, y;
    ld distSq() const { return x * x + y * y; }
    ld norm() const { return sqrt(distSq()); }
};

ld dist(Point a, Point b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

Point get_circumcenter(Point a, Point b, Point c) {
    ld d = 2 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
    if (abs(d) < 1e-9) return {1e18, 1e18};
    ld ux = ((a.x * a.x + a.y * a.y) * (b.y - c.y) + (b.x * b.x + b.y * b.y) * (c.y - a.y) + (c.x * c.x + c.y * c.y) * (a.y - b.y)) / d;
    ld uy = ((a.x * a.x + a.y * a.y) * (c.x - b.x) + (b.x * b.x + b.y * b.y) * (a.x - c.x) + (c.x * c.x + c.y * c.y) * (b.x - a.x)) / d;
    return {ux, uy};
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    ld s, t;
    if (!(cin >> n >> k >> s >> t)) return 0;

    vector<Point> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i].x >> p[i].y;

    vector<Point> candidates;
    candidates.push_back({0, 0});

    // 1. Midpoints & Star Positions
    for (int i = 0; i < n; ++i) {
        candidates.push_back(p[i]);
        for (int j = i + 1; j < n; ++j) {
            candidates.push_back({(p[i].x + p[j].x) / 2, (p[i].y + p[j].y) / 2});
        }
    }

    // 2. Circumcenters
    // Optimization: Only run for N <= 350 to stay within time limits for Subtask 5
    if (n <= 350) {
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int l = j + 1; l < n; ++l) {
                    Point cc = get_circumcenter(p[i], p[j], p[l]);
                    if (cc.x < 1e17) candidates.push_back(cc);
                }
            }
        }
    }

    ld min_total_cost = 1e30;

    for (Point c : candidates) {
        if (c.x > 1e17) continue;
        
        vector<ld> dists(n);
        for (int i = 0; i < n; ++i) dists[i] = dist(c, p[i]);
        
        nth_element(dists.begin(), dists.begin() + k - 1, dists.end());
        
        ld r = dists[k - 1];
        ld d = c.norm();
        min_total_cost = min(min_total_cost, (t * r) + (s * d));
    }

    cout << fixed << setprecision(10) << min_total_cost << endl;
    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...