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

Submission #10441676

Source Code Expand

Copy
```#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
//typedef pair<int, int> P;
const double EPS=1e-10;
if(abs(a+b)<EPS*(abs(a)+abs(b))) return 0;
return a+b;
}

struct P{
double x, y;
P() {}
P(double x, double y): x(x), y(y){
}
P operator+ (P p){
}
P operator- (P p){
}
P operator* (double d){
return P(x*d, y*d);
}
double dot(P p){
}
double det(P p){
}
bool operator< (const P& p) const{
if(abs(x-p.x)>EPS){
return x<p.x;
}else{
return y<p.y-EPS;
}
}
};
typedef pair<P, P> Ppair;
bool on_seg(P p1, P p2, P q){
return (p1-q).det(p2-q)==0 && (p1-q).dot(p2-q)<=0;
}

P intersection(P p1, P p2, P q1, P q2){
return p1+(p2-p1)*((q2-q1).det(q1-p1) / (q2-q1).det(p2-p1));
}

double dist(P p1, P p2){
return sqrt((p1-p2).dot(p1-p2));
}

double dist_ptseg(P p1, P p2, P q){
double d1=sqrt((p1-q).dot(p1-q)), d2=sqrt((p2-q).dot(p2-q));
if(abs(p1.x-p2.x)<EPS && abs(p1.y-p2.y)<EPS){
return d1;
}
P r=P((p2-p1).y, (p1-p2).x);
P s=intersection(p1, p2, q, q+r);
if(on_seg(p1, p2, s)){
return sqrt((q-s).dot(q-s));
}else{
return min(d1, d2);
}
}

double dist_segs(P p1, P p2, P q1, P q2){
if((q2-q1).det(p2-p1)!=0){
P r=intersection(p1, p2, q1, q2);
if(on_seg(p1, p2, r) && on_seg(q1, q2, r)) return 0;
}
double d1=dist_ptseg(p1, p2, q1), d2=dist_ptseg(p1, p2, q2), d3=dist_ptseg(q1, q2, p1), d4=dist_ptseg(q1, q2, p2);
double d=min(d1, min(d2, min(d3, d4)));
return d;
}

Ppair circ_intersection(P p1, double r1, P p2, double r2){ //2点で交わるか接する(同じ点を返す)
P q=(p2-p1)*((r1*r1-r2*r2-p1.dot(p1)+p2.dot(p2))/(2.0*((p2-p1).dot(p2-p1))));
P r=P((p2-p1).y, (p1-p2).x);
double sq=(r.dot(q-p1))*(r.dot(q-p1))-(r.dot(r))*((q-p1).dot(q-p1)-r1*r1);
if(abs(sq)<EPS){
sq=0;
}else{
sq=sqrt(sq);
}
double t1=(-(r.dot(q-p1))+sq)/(r.dot(r));
double t2=(-(r.dot(q-p1))-sq)/(r.dot(r));
P s1=q+r*t1, s2=q+r*t2;
return Ppair(s1, s2);
}
int main()
{
int n, k;
cin>>n>>k;
P p[100];
double c[100];
for(int i=0; i<n; i++){
cin>>p[i].x>>p[i].y>>c[i];
}
if(k==1){
cout<<0<<endl;
return 0;
}
auto count=[&](double d, P q){
int cnt=0;
for(int i=0; i<n; i++){
if(dist(p[i], q)<=d/c[i]+EPS) cnt++;
}
return cnt;
};
auto check=[&](double m){
for(int i=0; i<n; i++){
if(count(m, p[i])>=k) return true;
}
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
double d=dist(p[i], p[j]);
if(d<abs(m/c[i]-m/c[j])) continue;
if(d>m/c[i]+m/c[j]) continue;
auto pp=circ_intersection(p[i], m/c[i], p[j], m/c[j]);
if(count(m, pp.first)>=k) return true;
if(count(m, pp.second)>=k) return true;
}
}
return false;
};
double l=0, r=300000;
for(int loop=0; loop<100; loop++){
double m=(l+r)/2;
if(check(m)) r=m;
else l=m;
}
printf("%.7lf\n", r);
return 0;
}
```

#### Submission Info

Submission Time 2020-03-01 21:23:57+0900 F - Yakiniku Optimization Problem chocorusk C++14 (GCC 5.4.1) 600 3790 Byte AC 85 ms 256 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 1 ms 256 KB
00-sample-01 AC 2 ms 256 KB
01-handmade-00 AC 1 ms 256 KB
01-handmade-01 AC 1 ms 256 KB
01-handmade-02 AC 1 ms 256 KB
01-handmade-03 AC 71 ms 256 KB
01-handmade-04 AC 68 ms 256 KB
01-handmade-05 AC 59 ms 256 KB
01-handmade-06 AC 27 ms 256 KB
01-handmade-07 AC 38 ms 256 KB
01-handmade-08 AC 64 ms 256 KB
01-handmade-09 AC 65 ms 256 KB
01-handmade-10 AC 1 ms 256 KB
01-handmade-11 AC 1 ms 256 KB
02-random-00 AC 8 ms 256 KB
02-random-01 AC 60 ms 256 KB
02-random-02 AC 15 ms 256 KB
02-random-03 AC 58 ms 256 KB
02-random-04 AC 43 ms 256 KB
02-random-05 AC 8 ms 256 KB
02-random-06 AC 28 ms 256 KB
02-random-07 AC 13 ms 256 KB
02-random-08 AC 27 ms 256 KB
02-random-09 AC 23 ms 256 KB
02-random-10 AC 41 ms 256 KB
02-random-11 AC 32 ms 256 KB
02-random-12 AC 43 ms 256 KB
02-random-13 AC 25 ms 256 KB
02-random-14 AC 53 ms 256 KB
02-random-15 AC 25 ms 256 KB
02-random-16 AC 13 ms 256 KB
02-random-17 AC 6 ms 256 KB
02-random-18 AC 58 ms 256 KB
02-random-19 AC 58 ms 256 KB
02-random-20 AC 54 ms 256 KB
02-random-21 AC 55 ms 256 KB
02-random-22 AC 53 ms 256 KB
02-random-23 AC 82 ms 256 KB
02-random-24 AC 45 ms 256 KB
02-random-25 AC 13 ms 256 KB
02-random-26 AC 25 ms 256 KB
02-random-27 AC 13 ms 256 KB
02-random-28 AC 6 ms 256 KB
02-random-29 AC 37 ms 256 KB
02-random-30 AC 28 ms 256 KB
02-random-31 AC 70 ms 256 KB
02-random-32 AC 14 ms 256 KB
02-random-33 AC 60 ms 256 KB
02-random-34 AC 5 ms 256 KB
02-random-35 AC 53 ms 256 KB
02-random-36 AC 8 ms 256 KB
02-random-37 AC 57 ms 256 KB
02-random-38 AC 7 ms 256 KB
02-random-39 AC 85 ms 256 KB
02-random-40 AC 70 ms 256 KB
02-random-41 AC 35 ms 256 KB
02-random-42 AC 55 ms 256 KB
02-random-43 AC 85 ms 256 KB
02-random-44 AC 69 ms 256 KB
02-random-45 AC 83 ms 256 KB
02-random-46 AC 56 ms 256 KB
02-random-47 AC 13 ms 256 KB
02-random-48 AC 82 ms 256 KB
02-random-49 AC 80 ms 256 KB
03-killer-00 AC 6 ms 256 KB
03-killer-01 AC 6 ms 256 KB
03-killer-02 AC 4 ms 256 KB