更差的阅读体验
EI 牛逼！
首先很显然有至少一个点在圆上。否则一定可以通过调整使半径缩小。
那么我们枚举在圆上的一个点 \(p\)，则由于 \(r\) 满足单调性，可以二分。
考虑已知了半径 \(r\) 和圆上的一个点 \(p\)，要怎么判断是否存在一种画圆的方案使得包含至少 \(m\) 个点。那么我们考虑以 \(p\) 为端点的直径，对于另外一个点 \(i\)，使 \(i\) 在圆内的直径的极角一定使一个区间。如图两条红线的夹角即为点 \(i\) 所对应的极角区间。
把每个点的区间算出来，扫描线即可找出被最多个区间覆盖的极角。再将覆盖次数和 \(m\) 比大小即可。
对于每个 \(p\) 去二分，可以做到 \(O(n^2 \log n \log \frac{V}{\varepsilon})\)，过不了。
我们知道，对于每个 \(p\) 都客观存在着一个 \(r_i\) 表示 \(p\) 在圆上时，要覆盖 \(m\) 个点的最小半径（如果无法覆盖 \(m\) 个点则为 \(+\infty\)）。
我们还知道，对于一个 \(1 \sim n\) 的随机排列，期望有 \(O(\log n)\) 个前缀最小值。
考虑元素 \(x\) 作为前缀最小值的概率。
\(x\) 是排列的前缀最小值，当且仅当于 \(1, 2, \cdots, x-1\) 都出现在 \(x\) 出现的位置后面。
上述条件等价于，把 \(1 \sim x\) 的数字构成的子序列抽出来，\(x\) 排第一个的概率。
显然这个子序列可以看作随机序列，因此 \(x\) 作为前缀最小值的概率为 \(\frac{1}{x}\)。
因此期望前缀最小值个数为 \(\sum \limits _{i = 1}^n \frac{1}{n} = O(\ln n)\)。
这意味着，如果我们以随机的顺序来枚举 \(p\)，只有 \(O(\log n)\) 个位置会让答案变小！
具体地，我们使用随机顺序枚举 \(p\)，先 check 一下 \(p\) 的答案是否会比当前的 \(ans\) 小。如果会，我们再进行二分。由上面的分析，我们只会进行 \(O(\log n)\) 次二分。
所以总复杂度降到 \(O(n^2 \log n + n \log^2 n \log \frac{n}{\varepsilon})\)，其中前一部分是对每个 \(p\) check 一次的复杂度，可以通过。
#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
using namespace std;
template <typename T> inline T sq(T x) {return x*x;}
constexpr double eps=5e-8,pi=acos(-1);
int n,m,ord[N],tot;
double x[N],y[N],dis[N][N],ans=2e9;
pair<double,int> b[N<<1];
inline void trans(double &x) {if(x<eps)x+=2*pi;}
inline double get(double cs,double sn) //x, y
{if(fabs(cs)<eps&&fabs(sn)<eps)return 0;double ret=atan2(sn,cs); trans(ret);return ret;
}
int check(double mid,int p)
{tot=0;for(int i=1;i<=n;i++)if(i!=p&&dis[i][p]-mid*2<=eps){double t1=get(x[i]-x[p],y[i]-y[p]);double t2=acos(dis[i][p]/mid/2);b[++tot]={t1-t2,1},b[++tot]={t1+t2,-1};}sort(b+1,b+1+tot,[](pair<double,int> x,pair<double,int> y) {if(fabs(x.first-y.first)<eps*2)return x.second>y.second;return x.first<y.first;});int sum=1,ret=0;for(int i=1;i<=tot;i++)sum+=b[i].second,ret=max(ret,sum);return ret>=m;
}
main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=sqrt(sq(x[i]-x[j])+sq(y[i]-y[j]));for(int i=1;i<=n;i++)ord[i]=i;random_shuffle(ord+1,ord+1+n);for(int i=1;i<=n;i++){if(!check(ans,ord[i]))continue;double l=0,r=ans;while(r-l>eps){double mid=(l+r)/2;if(check(mid,ord[i]))r=mid,ans=mid;else l=mid;}}printf("%.10lf\n",ans);return 0;
}