题目描述

给定欧氏平面上的 \(n\) 个点，坐标分别为 \((x_1,y_1),\cdots,(x_n,y_n)\)。

求一个半径尽可能小的圆，使得至少有 \(k\) 个点落在圆内。你需要对半径给出一个 \((1+\varepsilon)\)-估计。

这里取 \(\varepsilon=0.1\)。

具体地，设最小的可能半径为 \(R^*\)，你的半径 \(R\) 必须满足 \(R^*\le R\le 1.1R^*\)。

输入格式

第一行两个数 \(n,k\)。

接下来 \(n\) 行，每行两个整数 \(x_i,y_i\)。

输出格式

仅一行三个数，依次表示你找出的圆的半径、圆心横坐标、圆心纵坐标。

输入输出样例 #1

输入 #1

4 2
0 0
0 1
1 0
1 1

输出 #1

0.5 0 0.5

说明/提示

样例 1 说明

显然 \(R^*=0.5\)，圆心设在 \((0.5,0),(1,0.5),(0.5,1)\) 显然也是可以的。

数据规模与约定

对于 \(100\%\) 的数据，都有 \(1\le n\le 10^5\)，\(-10^6\le x_i,y_i\le 10^6\)。