Problem: Problem

Great Demon King Megumi wants to defeat the $ N $ hero who lives on the ground.
Megumi can cast explosion magic up to $ M $ times.
Explosion magic is magic that extinguishes heroes who exist within a radius of $ r $ around arbitrary coordinates.
The hero is very thin, so you don't have to consider the size.
All $ M $ explosion spells shall be cast with the same radius.
I decided to use the magic of the minimum radius necessary to annihilate the hero.
Minimize the size of the explosive magic radius.

Constraints

The input satisfies the following conditions.

* $ 1 \ leq M \ leq N \ leq 14 $
* $ 0 \ leq x_i $, $ y_i \ leq 10 ^ 5 $

Input


$ N $ $ M $
$ x_1 $ $ y_1 $
...
$ x_N $ $ y_N $


The input is given in the following format.
The number of heroes $ N $ and the number of explosions to cast $ M $ are given as integers on the first line.
From the second line onward, the coordinates $ x_i $ $, $ $ y_i $ of each hero $ i $ are given as integers.

Output

Output the minimum value of the explosive magic radius as a real number.
Must not contain absolute error greater than $ 10 ^ {-3} $.

Examples

Input

5 2
0 0
5 5
10 10
100 100
200 200


Output

70.710678118755


Input

10 5
321 675
4312 6534
312 532
412 6543
21 43
654 321
543 0
32 5
41 76
5 1


Output

169.824909833728


Input

14 3
312 342
4893 432
321 4
389 4
23 543
0 0
1 1
2 2
432 12
435 32
1 5
2 10
100 100
20 50


Output

218.087711712613


Input

5 2
0 0
0 0
0 0
0 0
0 0


Output

0.000000000001

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
//#define EPS 0.000000001
using namespace std;



#define EPS 0.0000001

struct Point{
	Point(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}

	Point(){
		x = y = 0.0;
	}

	Point operator + (Point p){ return Point(x+p.x,y+p.y); }
	Point operator - (Point p){ return Point(x-p.x,y-p.y);}
	Point operator * (double a){ return Point(a*x,a*y); }
	Point operator / (double a){ return Point(x/a,y/a); }

	double abs(){ return sqrt(norm()); }
	double norm(){ return x*x + y*y; }

	bool operator<(const Point &p) const{
		return x != p.x? x < p.x: y < p.y;
	}

	bool operator == (const Point &p) const{
		return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
	}

	double x,y;
};

typedef Point Vector;

struct Line{
	Line(){

	}
	Line(Point a,Point b){
		p[0] = a;
		p[1] = b;
	}
	Point p[2];
};

int N,M;
int POW[15];
double dp[15][1 << 15];
double NUM = 20000000;
Point point[15];


double calc_dist(Point A,Point B){

	return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}


double calc_slope(Line A){

	if(fabs(A.p[0].x-A.p[1].x) < EPS){

		return DBL_MAX;

	}else if(fabs(A.p[0].y-A.p[1].y) < EPS){

		return 0;

	}else{

		return (A.p[1].y-A.p[0].y)/(A.p[1].x-A.p[0].x);
	}
}

//交点を求める関数
Point calc_Cross_Point(double x1,double x2,double x3,double x4,double y1,double y2,double y3,double y4){
	Point ret;
	ret.x = ((x2-x1)*(y3*(x4-x3)+x3*(y3-y4))-(x4-x3)*(y1*(x2-x1)+x1*(y1-y2)))/((y2-y1)*(x4-x3)-(y4-y3)*(x2-x1));
	if(x1 != x2){
		ret.y = ((y2-y1)*ret.x+y1*(x2-x1)+x1*(y1-y2))/(x2-x1);
	}else{
		ret.y = ((y4-y3)*ret.x+y3*(x4-x3)+x3*(y3-y4))/(x4-x3);
	}
	return ret;
}

//インタフェース関数
Point calc_Cross_Point(Point a,Point b,Point c,Point d){
	return calc_Cross_Point(a.x,b.x,c.x,d.x,a.y,b.y,c.y,d.y);
}

Point calc_minus(Point a,Point b){
    Point ret;

    ret.x = a.x-b.x;
    ret.y = a.y-b.y;

    return ret;
}

int func(double x1,double y1,double x2, double y2, double xp, double yp){
	double naiseki,norm1,norm2,gaiseki;
	norm1 = sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	norm2 = sqrt((xp-x1)*(xp-x1)+(yp-y1)*(yp-y1));
	naiseki = (xp-x1)*(x2-x1)+(yp-y1)*(y2-y1);
	gaiseki = (x2-x1)*(yp-y1)-(xp-x1)*(y2-y1);
	if(gaiseki > EPS){
		return 1;
	}else if(gaiseki < -EPS){
		return -1;
	}
	if(naiseki < -EPS){
		return 2;
	}

	if(norm1 < norm2){
		return -2;
	}
	return 0;
}


bool is_Cross(Line a,Line b){

	if(func(a.p[0].x,a.p[0].y,a.p[1].x,a.p[1].y,b.p[0].x,b.p[0].y)*
			func(a.p[0].x,a.p[0].y,a.p[1].x,a.p[1].y,b.p[1].x,b.p[1].y) <= 0 &&
			func(b.p[0].x,b.p[0].y,b.p[1].x,b.p[1].y,a.p[0].x,a.p[0].y)*
			func(b.p[0].x,b.p[0].y,b.p[1].x,b.p[1].y,a.p[1].x,a.p[1].y) <= 0){
		return true;
	}
	return false;
}

double calc_len(Vector a){
    return sqrt(a.x*a.x+a.y*a.y);
}

double norm(Vector a){
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a){
	return sqrt(norm(a));
}

double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

double dot(Vector a,Vector b){
    return a.x*b.x + a.y*b.y;
}

//線分ではなく直線と点の距離
double getDistanceLP(Line l,Point p){
    return fabs(cross(calc_minus(l.p[1],l.p[0]),calc_minus(p,l.p[0]))/calc_len(calc_minus(l.p[1],l.p[0])));
}

//点と線分の距離
double getDistanceSP(Line l,Point p){
	if(dot(calc_minus(l.p[1],l.p[0]),calc_minus(p,l.p[0])) < 0.0)return calc_len(calc_minus(p,l.p[0]));
	if(dot(calc_minus(l.p[0],l.p[1]),calc_minus(p,l.p[1])) < 0.0)return calc_len(calc_minus(p,l.p[1]));
	return getDistanceLP(l,p);
}

//線分と線分の距離
double getDistance(Line A,Line B){
	if(is_Cross(A,B))return 0.0;
	return min(min(getDistanceSP(A,B.p[0]),getDistanceSP(A,B.p[1])),
			min(getDistanceSP(B,A.p[0]),getDistanceSP(B,A.p[1])));
}

Point calc_Cross_Point(Line A,Line B){

	if(getDistanceSP(B,A.p[0]) < EPS){

		return A.p[0];

	}else if(getDistanceSP(B,A.p[1]) < EPS){

		return A.p[1];

	}else if(getDistanceSP(A,B.p[0]) < EPS){

		return B.p[0];

	}else if(getDistanceSP(A,B.p[1]) < EPS){

		return B.p[1];
	}

	return calc_Cross_Point(A.p[0],A.p[1],B.p[0],B.p[1]);
}

int main(){

	POW[0] = 1;
	for(int i = 1; i < 15; i++){

		POW[i] = POW[i-1]*2;
	}

	scanf("%d %d",&N,&M);

	for(int i = 0; i < N; i++){

		scanf("%lf %lf",&point[i].x,&point[i].y);
	}

	for(int i = 0; i <= M; i++){
		for(int state = 0; state < POW[N]; state++){

			dp[i][state] = BIG_NUM;
		}
	}

	vector<int> V;


	Line line1,line2;
	Point center;

	for(int state = 1; state < POW[N]; state++){

		V.clear();

		for(int loop = 0; loop < N; loop++){
			if(state & POW[loop]){

				V.push_back(loop);
			}
		}

		if(V.size() == 1){

			dp[1][state] = 0;
			//printf("dp[1][%d]:%.3lf\n",state,dp[1][state]);
			continue;

		}else if(V.size() == 2){

			dp[1][state] = calc_dist(point[V[0]],point[V[1]])/2;

			int work_state = state;

			center = Point((point[V[0]].x+point[V[1]].x)/2,(point[V[0]].y+point[V[1]].y)/2);

			for(int k = 0; k < N; k++){
				if(k == V[0] || k == V[1])continue;

				if(calc_dist(center,point[k]) <= dp[1][state]){

					work_state += POW[k];
				}
			}

			dp[1][work_state] = min(dp[1][work_state],dp[1][state]);

			continue;
		}

		//3点以上

		//2点を直径とする
		for(int a = 0; a < V.size()-1; a++){
			for(int b = a+1; b < V.size(); b++){

				center = Point((point[V[a]].x+point[V[b]].x)/2,(point[V[a]].y+point[V[b]].y)/2);

				double tmp_dist = calc_dist(point[V[a]],point[V[b]])/2;

				bool FLG = true;
				for(int k = 0; k < V.size(); k++){

					if(k == a || k == b)continue;

					if(calc_dist(center,point[V[k]]) > tmp_dist){
						FLG = false;
						break;
					}
				}

				if(FLG){

					dp[1][state] = min(dp[1][state],tmp_dist);
				}
			}
		}

		//3点を通る
		for(int a = 0; a < V.size()-2; a++){
			for(int b = a+1; b < V.size()-1; b++){
				for(int c = b+1; c < V.size(); c++){

					double slope1 = calc_slope(Line(point[V[a]],point[V[b]]));
					double slope2 = calc_slope(Line(point[V[b]],point[V[c]]));

					if(fabs(slope1-slope2) < EPS){ //一直線上

						continue;

					}else{

						Point mid1 = Point((point[V[a]].x+point[V[b]].x)/2,(point[V[a]].y+point[V[b]].y)/2);
						Point mid2 = Point((point[V[b]].x+point[V[c]].x)/2,(point[V[b]].y+point[V[c]].y)/2);

						if(fabs(slope1-DBL_MAX) < EPS){ //垂直

							line1.p[0] = Point(-NUM,mid1.y);
							line1.p[1] = Point(NUM,mid1.y);

						}else if(fabs(slope1) < EPS){ //水平

							line1.p[0] = Point(mid1.x,NUM);
							line1.p[1] = Point(mid1.x,-NUM);

						}else{

							slope1 = (-1.0)/slope1;

							line1.p[0] = Point(mid1.x-NUM,mid1.y-NUM*slope1);
							line1.p[1] = Point(mid1.x+NUM,mid1.y+NUM*slope1);
						}

						if(fabs(slope2-DBL_MAX) < EPS){ //垂直

							line2.p[0] = Point(-NUM,mid2.y);
							line2.p[1] = Point(NUM,mid2.y);

						}else if(fabs(slope2) < EPS){ //水平

							line2.p[0] = Point(mid2.x,NUM);
							line2.p[1] = Point(mid2.x,-NUM);

						}else{

							slope2 = (-1.0)/slope2;

							line2.p[0] = Point(mid2.x-NUM,mid2.y-NUM*slope2);
							line2.p[1] = Point(mid2.x+NUM,mid2.y+NUM*slope2);
						}

						center =  calc_Cross_Point(line1,line2);
					}


					double tmp_dist = calc_dist(center,point[V[a]]);

					bool FLG = true;
					for(int k = 0; k < V.size(); k++){

						if(k == a || k == b || k == c)continue;

						if(calc_dist(center,point[V[k]]) > tmp_dist){

							FLG = false;
							break;
						}
					}

					if(FLG){

						dp[1][state] = min(dp[1][state],tmp_dist);
					}
				}
			}

		}
	}


	int tmp_state;

	for(int state = 1; state < POW[N]-1; state++){

		V.clear();
		for(int loop = 0; loop < N; loop++){
			if(state & POW[loop]){

				//Do nothing

			}else{

				V.push_back(loop);
			}
		}

		for(int i = 1; i <= M-1; i++){
			if(fabs(dp[i][state]-BIG_NUM) < EPS)continue;

			for(int a = 1; a < POW[V.size()]; a++){ //足し合わせる状態

				tmp_state = 0;

				for(int loop = 0; loop < V.size(); loop++){
					if(a & POW[loop]){

						tmp_state += POW[V[loop]];
					}
				}

				dp[i+1][state+tmp_state] = min(dp[i+1][state+tmp_state],max(dp[i][state],dp[1][tmp_state]));
			}
		}
	}

	double ans = BIG_NUM;
	for(int i = 1; i <= M; i++){

		ans = min(ans,dp[i][POW[N]-1]);
	}

	printf("%.10lf\n",ans);

	return 0;
}