Submission #10933557


Source Code Expand

Copy
#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

Submission Time
Task F - Yakiniku Optimization Problem
User kotamanegi
Language C++14 (GCC 5.4.1)
Score 600
Code Size 4898 Byte
Status AC
Exec Time 879 ms
Memory 512 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 67
Set Name Test Cases
Sample 00-sample-00, 00-sample-01
All 00-sample-00, 00-sample-01, 01-handmade-00, 01-handmade-01, 01-handmade-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 01-handmade-08, 01-handmade-09, 01-handmade-10, 01-handmade-11, 02-random-00, 02-random-01, 02-random-02, 02-random-03, 02-random-04, 02-random-05, 02-random-06, 02-random-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39, 02-random-40, 02-random-41, 02-random-42, 02-random-43, 02-random-44, 02-random-45, 02-random-46, 02-random-47, 02-random-48, 02-random-49, 03-killer-00, 03-killer-01, 03-killer-02
Case Name Status Exec Time Memory
00-sample-00 AC 3 ms 384 KB
00-sample-01 AC 3 ms 256 KB
01-handmade-00 AC 1 ms 256 KB
01-handmade-01 AC 2 ms 256 KB
01-handmade-02 AC 21 ms 384 KB
01-handmade-03 AC 196 ms 384 KB
01-handmade-04 AC 741 ms 384 KB
01-handmade-05 AC 693 ms 384 KB
01-handmade-06 AC 469 ms 384 KB
01-handmade-07 AC 220 ms 384 KB
01-handmade-08 AC 584 ms 384 KB
01-handmade-09 AC 594 ms 384 KB
01-handmade-10 AC 2 ms 256 KB
01-handmade-11 AC 4 ms 256 KB
02-random-00 AC 45 ms 384 KB
02-random-01 AC 726 ms 384 KB
02-random-02 AC 51 ms 384 KB
02-random-03 AC 468 ms 384 KB
02-random-04 AC 416 ms 384 KB
02-random-05 AC 72 ms 384 KB
02-random-06 AC 231 ms 384 KB
02-random-07 AC 224 ms 384 KB
02-random-08 AC 155 ms 384 KB
02-random-09 AC 245 ms 384 KB
02-random-10 AC 617 ms 512 KB
02-random-11 AC 388 ms 384 KB
02-random-12 AC 546 ms 384 KB
02-random-13 AC 173 ms 384 KB
02-random-14 AC 521 ms 384 KB
02-random-15 AC 327 ms 384 KB
02-random-16 AC 174 ms 384 KB
02-random-17 AC 62 ms 384 KB
02-random-18 AC 531 ms 384 KB
02-random-19 AC 366 ms 384 KB
02-random-20 AC 543 ms 384 KB
02-random-21 AC 236 ms 384 KB
02-random-22 AC 503 ms 384 KB
02-random-23 AC 649 ms 384 KB
02-random-24 AC 706 ms 384 KB
02-random-25 AC 179 ms 384 KB
02-random-26 AC 247 ms 384 KB
02-random-27 AC 87 ms 384 KB
02-random-28 AC 42 ms 384 KB
02-random-29 AC 430 ms 384 KB
02-random-30 AC 451 ms 384 KB
02-random-31 AC 846 ms 384 KB
02-random-32 AC 109 ms 384 KB
02-random-33 AC 685 ms 384 KB
02-random-34 AC 39 ms 384 KB
02-random-35 AC 518 ms 384 KB
02-random-36 AC 63 ms 384 KB
02-random-37 AC 564 ms 384 KB
02-random-38 AC 53 ms 384 KB
02-random-39 AC 814 ms 384 KB
02-random-40 AC 482 ms 384 KB
02-random-41 AC 271 ms 384 KB
02-random-42 AC 343 ms 384 KB
02-random-43 AC 470 ms 384 KB
02-random-44 AC 772 ms 384 KB
02-random-45 AC 879 ms 384 KB
02-random-46 AC 466 ms 384 KB
02-random-47 AC 121 ms 384 KB
02-random-48 AC 822 ms 384 KB
02-random-49 AC 771 ms 384 KB
03-killer-00 AC 55 ms 384 KB
03-killer-01 AC 35 ms 384 KB
03-killer-02 AC 24 ms 384 KB