Submission #1344339

#TimeUsernameProblemLanguageResultExecution timeMemory
1344339s3narasiAstronomer (BOI23_astronomer)C++20
0 / 100
25 ms1468 KiB
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long double ld;

struct Point {
    ld x, y;
};

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

// Function to find the circumcenter of 3 points
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}; // Collinear points
    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() {
    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}); // Candidate 1: Origin

    // Candidate 2: Midpoints of every pair
    for (int i = 0; i < n; ++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});
        }
    }

    // Candidate 3: Circumcenters of every triple (Main O(N^3) part)
    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) {
        vector<ld> dists;
        for (int i = 0; i < n; ++i) {
            dists.push_back(dist(c, p[i]));
        }
        // Use nth_element for O(N) instead of O(N log N) sorting
        nth_element(dists.begin(), dists.begin() + k - 1, dists.end());
        
        ld r = dists[k - 1];
     ld d = sqrt(c.x * c.x + c.y * c.y);
        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...