Submission #1344471

#TimeUsernameProblemLanguageResultExecution timeMemory
1344471s3narasiAstronomer (BOI23_astronomer)C++20
0 / 100
2095 ms4540 KiB
#include <bits/stdc++.h>
using namespace std;

using ld = long double;

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

    int k, n;
    ld s, t;
    cin >> k >> n >> s >> t;

    vector<pair<ld, ld>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    auto dist = [&](ld x1, ld y1, ld x2, ld y2) {
        return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
    };

    ld ans = 1e18;

    vector<pair<ld, ld>> candidates;

    // 1. all stars as centers
    for (auto &p : a) candidates.push_back(p);

    // 2. midpoints of all pairs
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            ld mx = (a[i].first + a[j].first) / 2.0;
            ld my = (a[i].second + a[j].second) / 2.0;
            candidates.push_back({mx, my});
        }
    }

    // 3. also include origin (important!)
    candidates.push_back({0, 0});

    for (auto &c : candidates) {
        vector<ld> dists;
        for (auto &p : a) {
            dists.push_back(dist(c.first, c.second, p.first, p.second));
        }

        sort(dists.begin(), dists.end());

        ld r = dists[k-1]; // k-th closest star
        ld move_cost = s * dist(0, 0, c.first, c.second);
        ld build_cost = t * r;

        ans = min(ans, move_cost + build_cost);
    }

    cout << fixed << setprecision(10) << (double)ans << "\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...