Submission #10933557

---

Source Code Expand

#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-10L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL
#define seg_size 262144LL
#define MOD 998244353LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

typedef complex<long double> Point;
typedef pair<complex<long double>, complex<long double>> Line;

typedef struct Circle {
    complex<long double> center;
    long double r;
}Circle;

long double dot(Point a, Point b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}
long double cross(Point a, Point b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

long double Dist_Line_Point(Line a, Point b) {
    if (dot(a.second - a.first, b - a.first) < eps) return abs(b - a.first);
    if (dot(a.first - a.second, b - a.second) < eps) return abs(b - a.second);
    return abs(cross(a.second - a.first, b - a.first)) / abs(a.second - a.first);
}

int is_intersected_ls(Line a, Line b) {
    return (cross(a.second - a.first, b.first - a.first) * cross(a.second - a.first, b.second - a.first) < 0) &&
        (cross(b.second - b.first, a.first - b.first) * cross(b.second - b.first, a.second - b.first) < 0);
}

Point intersection_l(Line a, Line b) {
    Point da = a.second - a.first;
    Point db = b.second - b.first;
    return a.first + da * cross(db, b.first - a.first) / cross(db, da);
}

long double Dist_Line_Line(Line a, Line b) {
    if (is_intersected_ls(a, b) == 1) {
        return 0;
    }
    return min({ Dist_Line_Point(a,b.first), Dist_Line_Point(a,b.second),Dist_Line_Point(b,a.first),Dist_Line_Point(b,a.second) });
}

pair<Point, Point> intersection_Circle_Circle(Circle a, Circle b) {
    long double dist = abs(a.center - b.center);
    assert(dist <= eps + a.r + b.r);
    assert(dist+eps >= abs(a.r - b.r));
    Point target = b.center - a.center;
    long double pointer = target.real() * target.real() + target.imag() * target.imag();
    long double aa = pointer + a.r * a.r - b.r * b.r;
    aa /= 2.0L;
    Point l{ (aa * target.real() + target.imag() * sqrt(pointer * a.r * a.r - aa * aa))/pointer,
            (aa* target.imag() - target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer};
    Point r{ (aa * target.real() - target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,
        (aa * target.imag() + target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };
    r = r + a.center;
    l = l + a.center;
    return mp(l, r);
}
void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

#define int ll
void solve(){/*
    long double a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    pair<Point, Point> now = intersection_Circle_Circle(Circle{ Point{a,b},c }, Circle{ Point{d,e}, f });
    cout << now.first << " " << now.second << endl;
    return;
    */
    int n, k;
    cin >> n >> k;
    vector<Circle> inputs;
    REP(i, n) {
        long double a, b, c;
        cin >> a >> b >> c;
        inputs.push_back(Circle{ Point{a,b}, c });
    }
    long double bot = 1e9;
    long double top = 0;
    REP(tea, 200) {
        long double mid = (bot + top) / 2;
        vector<Circle> now;
        REP(i, n) {
            now.push_back(Circle{ inputs[i].center, mid / inputs[i].r });
        }
        vector<Point> kouho;
        int ok = 0;
        REP(i, now.size()) {
            kouho.push_back(now[i].center);
            for (int q = i + 1; q < now.size(); ++q) {
                long double dist = abs(now[i].center - now[q].center);
                if (dist <= eps + now[i].r + now[q].r && dist + eps >= abs(now[i].r - now[q].r)) {
                    pair<Point, Point> tmp = intersection_Circle_Circle(now[i], now[q]);
                    kouho.push_back(tmp.first);
                    kouho.push_back(tmp.second);
                }
            }
        }
        REP(i, kouho.size()) {
            int cnt = 0;
            REP(q, now.size()) {
                if (abs(kouho[i] - now[q].center) <= eps + now[q].r) {
                    cnt++;
                }
            }
            if (cnt >= k) {
                ok = 1;
                break;
            }
        }
        if (ok == 1) bot = mid;
        else top = mid;
    }
    cout << bot << endl;
}

#undef int
int main() {
    init();
    solve();
}

Submission Info

Judge Result