Contest Duration: - (local time) (100 minutes) Back to Home

Submission #10933557

Source Code Expand

Copy
```#define  _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#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 2020-03-16 13:47:09+0900 F - Yakiniku Optimization Problem kotamanegi C++14 (GCC 5.4.1) 600 4898 Byte AC 879 ms 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
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