小葱同学今天学会了复制，于是我们现在有N个小葱同学。N个小葱同学每人有一把弹弓，并且第i个小葱同学站在((x_i, y_i))的位置上。现在所有的小葱同学希望把弹弓的射程调到某一个值，使得在这个射程下，存在M个小葱同学，这M个小葱同学之之间任意两位都可以互相射击到。问这个距离最小是多少。
【输入格式】
第一行两个数N,M
接下来N行每行两个整数代表小葱同学的坐标
【输出格式】
输出一行一个六位小数代表答案
【样例】
4 3
0 0
0 1
1 1
1 0
【输出】
1.414212
【数据规模与约定】
对于30%的数据，(N leq 10)
对于另外10%的数据，(M = 2)
对于另外20%的数据，(M = 3)
对于80%的数据，(M leq 50)
对于100%的数据，(1 leq M leq N leq 200, |x|, |y| leq 10^4)
Solution
看题意似乎是让我们求一个最大团，但这在普通图里是个NPC问题，那有什么特殊图能做吗？
二分图可以。因为二分图相当于两个点集，每个点集之内的点相互之间都有边，两个点集之间又有一些边。所有就相当于要找一个最大匹配。这个显然可以求。
但是，哪里来的二分图呢？
考虑这是一个坐标图，任意两点的连线会有上面的一部分和下面的一部分。当我们选中两个点，并以两个点的距离为半径画圆的时候，这两个圆会有一个相交的集合。将这个集合分成两半，一半在两点连线的上面，一半在下面。这两个点集的内部的点的距离一定小于等于选中两点之间的距离，而两个点集之间的点不一定。所以这就形成了一个二分图。
至于怎么判断某个点是属于上面一个集合还是下面的，用向量的叉乘就好了。
所有，我们首先二分一个距离，然后找到所有满足距离小于等于这个距离的点对，再以每个点对画圆，构建二分图，统计每个二分图的最大匹配。如果这个匹配大于等于M，就说明OK，反之不行。
这里要注意一点，二分图不能直接求最大匹配，因为我们实际上要求的是一个最大团，所以要求一个反图的最大匹配。最大团 = 反图最大独立集 = 总点数 - 反图最大匹配
这题就这样做完了qwq
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int n, m, l, r, p[2][210], re[210], x[210], y[210];
bool use[210];
int c, dis[210][210], d[210 * 210];
inline int cross(int x1, int y1, int x2, int y2) {//叉乘
return x1 * y2 - x2 * y1;
}
inline bool dfs(int now) {//求最大匹配
for (int i = 1; i <= r; ++i)
if (!use[i] && dis[p[0][now]][p[1][i]] > c) {//因为是反图，所以找距离大于c的
use[i] = 1;
if (!re[i] || dfs(re[i])) {
re[i] = now; return 1;
}
}
return 0;
}
inline bool check(int d) {
if (m == 1) return 1;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (dis[i][j] <= d) {
if (m == 2) return 1;
l = 0, r = 0;
for (int k = 1; k <= n; ++k)
if (k != i && k != j && dis[i][k] <= dis[i][j] && dis[j][k] <= dis[i][j]) {
//判断这个节点是否在两个圆的交集内，并划分集合
if (cross(x[k] - x[i], y[k] - y[i], x[j] - x[i], y[j] - y[i]) <= 0) p[0][++l] = k;
else p[1][++r] = k;
}
c = d;
memset(re, 0, sizeof re);
int ans = 0;
for (int k = 1; k <= l; ++k) {//求匹配
memset(use, 0, sizeof use);
if (dfs(k)) ans++;
}
ans = l + r - ans + 2;//统计答案
if (ans >= m) return 1;
}
return 0;
}
int main() {
freopen("die.in", "r", stdin);
freopen("die.out", "w", stdout);
scanf("%d%d", &n, &m);
if (m == 1) {
printf("0.000000
"); return 0;
}
for (int i = 1; i <= n; ++i)
scanf("%d%d", &x[i], &y[i]);
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {//计算出两点之间的距离
dis[i][j] = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
//直接存储平方
d[++cnt] = dis[i][j];//二分的数组
}
sort(d + 1, d + 1 + cnt);
int l = 0, r = cnt, u = cnt;
while (l < r) {
int mid = (l + r) >> 1;
if (check(d[mid])) u = mid, r = mid - 1;
else l = mid + 1;
}
printf("%.6lf
", sqrt(d[u]));
return 0;
}