#P1946. [Ceoi2006]ANTENNA

    ID: 968 传统题 2000ms 64MiB 尝试: 87 已通过: 15 难度: 7 上传者: 标签>CF2300提高+/省选-二分答案实数二分暴力枚举扫描线环形区间拆分事件同坐标排序

[Ceoi2006]ANTENNA

[CEOI2006] ANTENNA

题目描述

给出 NN 个点的坐标,要求能够覆盖其中至少 KK 个点的圆的最小半径及圆心位置。

输入格式

第一行两个整数 N,KN,K。

接下来的 NN 行,每行两个整数,为每个点的坐标。

输出格式

第一行为圆的半径。

第二行为圆心的坐标。

使用 SPJ,满足以下两个条件才正确:

  • RR 误差不超过 10−410^{-4}。

  • 虽然多组解可以输出任意一组,但以你输出的坐标为圆心的圆如果以 R+0.0002R+0.0002为半径至少应该覆盖 KK个点。

样例 #1

样例输入 #1

10 5 
1 8 
2 6 
4 8 
2 2 
9 7 
8 5 
5 3 
3 3 
4 6 
4 1

样例输出 #1

2.236068 
3 4

提示

对于 100%100\% 的数据, 2≤K≤N≤5002\le K\le N\le 500,0≤X,Y≤1040\le X,Y\le 10^4。