Language: C++

#pragma GCC optimize ("Ofast")
#pragma GCC target("native")
#pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define PI 3.14159265358979323846
void *wmem;
char memarr[96000000];
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T1> void sortA_L(int N, T1 a[], void *mem = wmem){
  sort(a, a+N);
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(double &x){
  scanf("%lf",&x);
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(double x){
  printf("%.15f",x);
}
template<class T> inline T pow2_L(T a){
  return a*a;
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
#define EPS 1e-10
int N;
int K;
double X[60];
double Y[60];
int C[60];
struct pnt{
  double x;
  double y;
}
;
struct line{
  pnt a;
  pnt b;
}
;
struct circle{
  pnt c;
  double r;
}
;
pnt p[60];
int doubleSign(double a){
  if(a>EPS){
    return 1;
  }
  if(a<-EPS){
    return -1;
  }
  return 0;
}
int doubleSignR(double a,double b){
  if(doubleSign(b)!=0 && doubleSign(a/b-1)==0){
    return 0;
  }
  return doubleSign(a-b);
}
int pntSign(pnt a){
  int i=doubleSign(a.x);
  if(i){
    return i;
  }
  return doubleSign(a.y);
}
pnt pntPlus(pnt a,pnt b){
  a.x+=b.x;
  a.y+=b.y;
  return a;
}
pnt pntMinus(pnt a,pnt b){
  a.x-=b.x;
  a.y-=b.y;
  return a;
}
pnt pntMultiple(pnt a,pnt b){
  pnt c;
  c.x=a.x*b.x-a.y*b.y;
  c.y=a.x*b.y+a.y*b.x;
  return c;
}
pnt pntMultipleDouble(pnt a,double k){
  a.x*=k;
  a.y*=k;
  return a;
}
pnt pntPolar(double r,double t){
  pnt a;
  a.x=r*cos(t);
  a.y=r*sin(t);
  return a;
}
int pntIsEqual(pnt a,pnt b){
  return pntSign(pntMinus(a,b))==0;
}
pnt pntRatation(pnt a,pnt o,double t){
  return pntPlus(pntMultiple(pntMinus(a,o),pntPolar(1.0,t)),o);
}
pnt pntRatationEasy(pnt a,double t){
  return pntMultiple(a,pntPolar(1.0,t));
}
line perpendicularBisectorOfSegment(pnt a, pnt b){
  line res;
  pnt mid;
  pnt dir;
  mid = pntMultipleDouble(pntPlus(a,b),0.5);
  dir = pntRatationEasy( pntMinus(b,a), PI/2 );
  res.a = pntMinus(mid,dir);
  res.b = pntPlus(mid,dir);
  return res;
}
int doubleSolveSecondDegreeEquation(double a,double b,double c,double *res1,double *res2){
  if(doubleSign(a)){
    double d=b*b-4*a*c;
    int m=doubleSign(d)+1;
    if(m==1){
      *res1=-b/(2*a);
    }
    if(m==2){
      d=sqrt(d);
      *res1=(-b-d)/(2*a);
      *res2=(-b+d)/(2*a);
    }
    return m;
  }
  if(doubleSign(b)){
    *res1 = -b/c;
    return 1;
  }
  if(doubleSign(c)){
    return 0;
  }
  return 3;
}
int pntIntersectionLineCircle(line t,circle s,pnt *res1,pnt *res2){
  int m;
  double a;
  double b;
  double c;
  double t1;
  double t2;
  double k1;
  double k2;
  pnt ab=pntMinus(t.b, t.a);
  a=b=0;
  c=-s.r*s.r;
  t1=t.a.x-s.c.x;
  t2=t.b.x-t.a.x;
  a+=t2*t2;
  b+=2*t1*t2;
  c+=t1*t1;
  t1=t.a.y-s.c.y;
  t2=t.b.y-t.a.y;
  a+=t2*t2;
  b+=2*t1*t2;
  c+=t1*t1;
  m=doubleSolveSecondDegreeEquation(a,b,c,&k1,&k2);
  if(m>=1){
    *res1 = pntPlus( t.a, pntMultipleDouble(ab,k1) );
  }
  if(m>=2){
    *res2 = pntPlus( t.a, pntMultipleDouble(ab,k2) );
  }
  return m;
}
line pntGetLineFromCoefficient(double a,double b,double c){
  line res;
  if( doubleSign(a)==0 ){
    res.a.x = 0;
    res.b.x = 1;
    res.a.y = res.b.y = -c/b;
  }
  else{
    res.a.y=0;
    res.b.y=1;
    res.a.x=-c/a;
    res.b.x=(-b-c)/a;
  }
  return res;
}
int pntIntersectionCircleCircle(circle s1,circle s2,pnt *res1,pnt *res2){
  double a;
  double b;
  double c;
  line t;
  double x1=s1.c.x;
  double x2=s2.c.x;
  double y1=s1.c.y;
  double y2=s2.c.y;
  double r1=s1.r;
  double r2=s2.r;
  if( pntIsEqual(s1.c,s2.c) ){
    if( doubleSign(s1.r-s2.r)==0 ){
      return 3;
    }
    return 0;
  }
  a = 2*(x1-x2);
  b = 2*(y1-y2);
  c = (x2*x2-x1*x1) + (y2*y2-y1*y1) - (r2*r2-r1*r1);
  t = pntGetLineFromCoefficient(a,b,c);
  return pntIntersectionLineCircle(t,s1,res1,res2);
}
int pntIntersectionLineLine(line s,line t,pnt *res){
  pnt p1=s.a;
  pnt p2=s.b;
  pnt p3=t.a;
  pnt p4=t.b;
  double r = (p4.y-p3.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p4.x-p3.x);
  if( doubleSign(r)==0 ){
    return 0;
  }
  res->x = (p3.x*p4.y-p3.y*p4.x)*(p2.x-p1.x)-(p1.x*p2.y-p1.y*p2.x)*(p4.x-p3.x);
  res->y = (p3.y*p4.x-p3.x*p4.y)*(p2.y-p1.y)-(p1.y*p2.x-p1.x*p2.y)*(p4.y-p3.y);
  res->x /= r;
  res->y /= -r;
  return 1;
}
int cs;
int ls;
circle c[4000];
line l[4000];
double arr[60];
double eval(double x, double y){
  int i;
  for(i=(0);i<(N);i++){
    arr[i] = C[i] * sqrt(pow2_L((X[i]-x))+pow2_L((Y[i]-y)));
  }
  sortA_L(N,arr);
  return arr[K-1];
}
int main(){
  int i;
  wmem = memarr;
  int k;
  double x;
  double y;
  double x1;
  double y1;
  double x2;
  double y2;
  double res = 1e150;
  pnt p1;
  pnt p2;
  rd(N);
  rd(K);
  {
    int Q5VJL1cS;
    for(Q5VJL1cS=(0);Q5VJL1cS<(N);Q5VJL1cS++){
      rd(X[Q5VJL1cS]);
      rd(Y[Q5VJL1cS]);
      rd(C[Q5VJL1cS]);
    }
  }
  for(i=(0);i<(N);i++){
    p[i].x = X[i];
    p[i].y = Y[i];
  }
  for(i=(0);i<(N);i++){
    chmin(res, eval(X[i], Y[i]));
  }
  for(i=(0);i<(N);i++){
    int j;
    for(j=(i+1);j<(N);j++){
      x = (C[i] * X[i] + C[j] * X[j]) / (C[i] + C[j]);
      y = (C[i] * Y[i] + C[j] * Y[j]) / (C[i] + C[j]);
      chmin(res, eval(x, y));
    }
  }
  for(i=(0);i<(N);i++){
    int j;
    for(j=(i+1);j<(N);j++){
      if(C[i] == C[j]){
        l[ls++] = perpendicularBisectorOfSegment(p[i], p[j]);
      }
      else{
        x1 = (C[i] * X[i] + C[j] * X[j]) / (C[i] + C[j]);
        y1 = (C[i] * Y[i] + C[j] * Y[j]) / (C[i] + C[j]);
        x2 = (C[i] * X[i] - C[j] * X[j]) / (C[i] - C[j]);
        y2 = (C[i] * Y[i] - C[j] * Y[j]) / (C[i] - C[j]);
        c[cs].c.x = (x1 + x2) / 2;
        c[cs].c.y = (y1 + y2) / 2;
        c[cs++].r = sqrt(pow2_L((x1-x2))+pow2_L((y1-y2))) / 2;
      }
    }
  }
  for(i=(0);i<(cs);i++){
    int j;
    for(j=(i+1);j<(cs);j++){
      k = pntIntersectionCircleCircle(c[i],c[j],&p1,&p2);
      if(k>=1){
        chmin(res, eval(p1.x, p1.y));
      }
      if(k>=2){
        chmin(res, eval(p2.x, p2.y));
      }
    }
  }
  for(i=(0);i<(ls);i++){
    int j;
    for(j=(i+1);j<(ls);j++){
      k = pntIntersectionLineLine(l[i], l[j], &p1);
      if(k==1){
        chmin(res, eval(p1.x, p1.y));
      }
    }
  }
  for(i=(0);i<(ls);i++){
    int j;
    for(j=(0);j<(cs);j++){
      k = pntIntersectionLineCircle(l[i],c[j],&p1,&p2);
      if(k>=1){
        chmin(res, eval(p1.x, p1.y));
      }
      if(k>=2){
        chmin(res, eval(p2.x, p2.y));
      }
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay varsion 20200227-1

// --- original code ---
// #define EPS 1e-10
// 
// int N, K;
// double X[60], Y[60]; int C[60];
// 
// struct pnt{double x,y;};
// struct line{pnt a,b;};
// struct circle{pnt c; double r;};
// 
// pnt p[60];
// 
// 
// int doubleSign(double a){if(a>EPS) return 1; if(a<-EPS) return -1; return 0;}
// int doubleSignR(double a,double b){ if(doubleSign(b)!=0 && doubleSign(a/b-1)==0) return 0; return doubleSign(a-b);}
// int pntSign(pnt a){int i=doubleSign(a.x); if(i) return i; return doubleSign(a.y);}
// 
// pnt pntPlus(pnt a,pnt b){a.x+=b.x; a.y+=b.y; return a;}
// pnt pntMinus(pnt a,pnt b){a.x-=b.x; a.y-=b.y; return a;}
// pnt pntMultiple(pnt a,pnt b){pnt c; c.x=a.x*b.x-a.y*b.y; c.y=a.x*b.y+a.y*b.x; return c;}
// pnt pntMultipleDouble(pnt a,double k){a.x*=k; a.y*=k; return a;}
// pnt pntPolar(double r,double t){pnt a; a.x=r*cos(t); a.y=r*sin(t); return a;}
// 
// int pntIsEqual(pnt a,pnt b){return pntSign(pntMinus(a,b))==0;}
// 
// pnt pntRatation(pnt a,pnt o,double t){
//   return pntPlus(pntMultiple(pntMinus(a,o),pntPolar(1.0,t)),o);
// }
// 
// pnt pntRatationEasy(pnt a,double t){
//   return pntMultiple(a,pntPolar(1.0,t));
// }
// 
// 
// line perpendicularBisectorOfSegment(pnt a, pnt b){
//   line res; pnt mid, dir;
//   mid = pntMultipleDouble(pntPlus(a,b),0.5);
//   dir = pntRatationEasy( pntMinus(b,a), PI/2 );
//   res.a = pntMinus(mid,dir); res.b = pntPlus(mid,dir);
//   return res;
// }
// 
// int doubleSolveSecondDegreeEquation(double a,double b,double c,double *res1,double *res2){
//   if(doubleSign(a)){
//     double d=b*b-4*a*c; int m=doubleSign(d)+1;
//     if(m==1) *res1=-b/(2*a);
//     if(m==2){d=sqrt(d); *res1=(-b-d)/(2*a); *res2=(-b+d)/(2*a);}
//     return m;
//   }
//   if(doubleSign(b)){*res1 = -b/c; return 1;}
//   if(doubleSign(c)) return 0; return 3;
// }
// 
// int pntIntersectionLineCircle(line t,circle s,pnt *res1,pnt *res2){
//   int m; double a,b,c,t1,t2,k1,k2; pnt ab=pntMinus(t.b, t.a);
//   a=b=0; c=-s.r*s.r;
//   t1=t.a.x-s.c.x; t2=t.b.x-t.a.x; a+=t2*t2; b+=2*t1*t2; c+=t1*t1;
//   t1=t.a.y-s.c.y; t2=t.b.y-t.a.y; a+=t2*t2; b+=2*t1*t2; c+=t1*t1;
//   m=doubleSolveSecondDegreeEquation(a,b,c,&k1,&k2);
//   if(m>=1) *res1 = pntPlus( t.a, pntMultipleDouble(ab,k1) );
//   if(m>=2) *res2 = pntPlus( t.a, pntMultipleDouble(ab,k2) );
//   return m;
// }
// 
// line pntGetLineFromCoefficient(double a,double b,double c){
//   line res;
//   if( doubleSign(a)==0 ){
//     res.a.x = 0; res.b.x = 1;
//     res.a.y = res.b.y = -c/b;
//   } else {
//     res.a.y=0; res.b.y=1;
//     res.a.x=-c/a; res.b.x=(-b-c)/a;
//   }
//   return res;
// }
// 
// int pntIntersectionCircleCircle(circle s1,circle s2,pnt *res1,pnt *res2){
//   double a,b,c; line t;
//   double x1=s1.c.x, x2=s2.c.x, y1=s1.c.y, y2=s2.c.y, r1=s1.r, r2=s2.r;
//   if( pntIsEqual(s1.c,s2.c) ){ if( doubleSign(s1.r-s2.r)==0 ) return 3; return 0; }
//   a = 2*(x1-x2); b = 2*(y1-y2);
//   c = (x2*x2-x1*x1) + (y2*y2-y1*y1) - (r2*r2-r1*r1);
//   t = pntGetLineFromCoefficient(a,b,c);
//   return pntIntersectionLineCircle(t,s1,res1,res2);
// }
// 
// int pntIntersectionLineLine(line s,line t,pnt *res){
//   pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b;
//   double r = (p4.y-p3.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p4.x-p3.x);
//   if( doubleSign(r)==0 ) return 0;
//   res->x = (p3.x*p4.y-p3.y*p4.x)*(p2.x-p1.x)-(p1.x*p2.y-p1.y*p2.x)*(p4.x-p3.x);
//   res->y = (p3.y*p4.x-p3.x*p4.y)*(p2.y-p1.y)-(p1.y*p2.x-p1.x*p2.y)*(p4.y-p3.y);
//   res->x /= r; res->y /= -r; return 1;
// }
// 
// 
// int cs;
// int ls;
// circle c[4000];
// line l[4000];
// 
// double arr[60];
// double eval(double x, double y){
//   rep(i,N) arr[i] = C[i] * sqrt( (X[i]-x)**2 + (Y[i]-y)**2 );
//   sortA(N,arr);
//   return arr[K-1];
// }
// 
// {
//   int k;
//   double x, y, x1, y1, x2, y2;
//   double res = double_inf;
//   pnt p1;
//   pnt p2;
//   rd(N,K,(X,Y,C)(N));
// 
//   rep(i,N) p[i].x = X[i], p[i].y = Y[i];
// 
//   rep(i,N) res <?= eval(X[i], Y[i]);
//   rep(i,N) rep(j,i+1,N){
//     x = (C[i] * X[i] + C[j] * X[j]) / (C[i] + C[j]);
//     y = (C[i] * Y[i] + C[j] * Y[j]) / (C[i] + C[j]);
//     res <?= eval(x, y);
//   }
// 
//   rep(i,N) rep(j,i+1,N){
//     if(C[i] == C[j]){
//       l[ls++] = perpendicularBisectorOfSegment(p[i], p[j]);
//     } else {
//       x1 = (C[i] * X[i] + C[j] * X[j]) / (C[i] + C[j]);
//       y1 = (C[i] * Y[i] + C[j] * Y[j]) / (C[i] + C[j]);
//       x2 = (C[i] * X[i] - C[j] * X[j]) / (C[i] - C[j]);
//       y2 = (C[i] * Y[i] - C[j] * Y[j]) / (C[i] - C[j]);
//       c[cs].c.x = (x1 + x2) / 2;
//       c[cs].c.y = (y1 + y2) / 2;
//       c[cs++].r = sqrt( (x1-x2)**2 + (y1-y2)**2 ) / 2;
//     }
//   }
// 
//   rep(i,cs) rep(j,i+1,cs){
//     k = pntIntersectionCircleCircle(c[i],c[j],&p1,&p2);
//     if(k>=1) res <?= eval(p1.x, p1.y);
//     if(k>=2) res <?= eval(p2.x, p2.y);
//   }
// 
//   rep(i,ls) rep(j,i+1,ls){
//     k = pntIntersectionLineLine(l[i], l[j], &p1);
//     if(k==1) res <?= eval(p1.x, p1.y);
//   }
// 
//   rep(i,ls) rep(j,cs){
//     k = pntIntersectionLineCircle(l[i],c[j],&p1,&p2);
//     if(k>=1) res <?= eval(p1.x, p1.y);
//     if(k>=2) res <?= eval(p2.x, p2.y);
//   }
// 
//   wt(res);
// }


Compiler output:
cc1plus: error: attribute 'target' argument 'native' is unknown
cc1plus: error: attribute 'target' argument 'native' is unknown