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;
double add(double a, double b){
    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){
        return P(add(x, p.x), add(y, p.y));
    }
    P operator- (P p){
        return P(add(x, -p.x), add(y, -p.y));
    }
    P operator* (double d){
        return P(x*d, y*d);
    }
    double dot(P p){
        return add(x*p.x, y*p.y);
    }
    double det(P p){
        return add(x*p.y, -y*p.x);
    }
    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
Task F - Yakiniku Optimization Problem
User chocorusk
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3790 Byte
Status AC
Exec Time 85 ms
Memory 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
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 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