Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const long double PI = 4 * atan(1);
- int n, k;
- pair<long double, long double> points[500], centered, ans;
- bool check(long double r) {
- for (int i = 0; i < n; i++) {
- vector<pair<long double, int>> events;
- for (int j = 0; j < n; j++) if (j != i) {
- long double dist = hypot(points[j].second - points[i].second, points[j].first - points[i].first);
- if (dist > 2 * r) continue;
- long double a = atan2(points[j].second - points[i].second, points[j].first - points[i].first);
- long double b = acos(dist / (2 * r));
- events.push_back({a - b, 1});
- events.push_back({a + b, -1});
- events.push_back({a - b + 2 * PI, 1});
- events.push_back({a + b + 2 * PI, -1});
- }
- sort(events.begin(), events.end());
- int cnt = 1;
- for (pair<long double, int> j : events) {
- cnt += j.second;
- if (cnt >= k) return centered = {points[i].first + r * cos(j.first), points[i].second + r * sin(j.first)}, true;
- }
- }
- return false;
- }
- int main() {
- ios_base::sync_with_stdio(0), cin.tie(0);
- cin >> n >> k;
- for (int i = 0; i < n; i++) {
- cin >> points[i].first >> points[i].second;
- }
- long double l = 0, r = 7500;
- while (abs(r - l) > 1e-5) {
- long double mid = (l + r) / 2;
- if (check(mid)) r = mid;
- else l = mid;
- }
- cout << fixed << setprecision(5) << l << '\n' << centered.first << ' ' << centered.second;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
