2663: [Beijing wc2012]灵魂宝石
Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 261 Solved: 108
[Submit][Status][Discuss]
Description
“作为你们本体的灵魂，为了能够更好的运用魔法，被赋予了既小巧又安全
的外形，„„”
我们知道，魔法少女的生命被存放于一个称为灵魂宝石（Soul Gem）的装置
内。而有时，当灵魂宝石与躯体的距离较远时，魔法少女就无法控制自己的躯体
了。
在传说中，魔法少女 Abel仅通过推理就得到了这个现象的一般法则，被称为
Abel定理：
存在宇宙常量 R（是一个非负实数，或正无穷） ，被称为灵魂宝石常量，量
纲为空间度量（即：长度） 。如果某个魔法少女的灵魂宝石与她的躯体的距离严
格超过 R，则她一定无法控制自己的躯体；如果这个距离严格小于 R，则她一定
可以控制自己的躯体。 （这里的距离指平面的 Euclid距离。）
注意：该定理不能预言距离刚好为 R 的情形。可能存在魔法少女 A 和 B，她
们离自己的灵魂宝石的距离都恰好为 R，但是 A可以控制自己的躯体，而 B 不可
以。
现在这个世界上再也没有魔法少女了，但是我们却对这个宇宙常量感兴趣。
我们只能通过之前的世界遗留下来的数据来确定这个常量的范围了。
每一组数据包含以下信息：
·一共有N 个魔法少女及她们的灵魂宝石，分别编号为 1~N。
·这 N个魔法少女所在的位置是（Xi, Yi）。
·这 N个灵魂宝石所在的位置是（xi, yi）。
·此时恰好有 K个魔法少女能够控制自己的躯体。
需要注意的是：
1. 我们认为这个世界是二维的 Euclid 空间。
2. 魔法少女与灵魂宝石之间的对应关系是未知的。
3. 我们不知道是具体是哪 K个魔法少女能够控制自己的躯体。
根据以上信息，你需要确定灵魂宝石常量 R可能的最小值 Rmin 和最大值
Rmax。
Input
第一行包两个整数：N、K。
接下来 N行，每行包含两个整数：Xi , Yi ，由空格隔开。
再接下来N 行，每行包含两个整数：xi , yi ，由空格隔开。
Output
输出两个量：Rmin、Rmax，中间用空格隔开。
Rmin 一定是一个非负实数，四舍五入到小数点后两位。
Rmax 可能是非负实数，或者是正无穷：
如果是非负实数，四舍五入到小数点后两位；
如果是正无穷，输出“+INF”（不包含引号）。
Sample Input
1 0
4 0
0 0
4 4
Sample Output
HINT
对于100%的数据：
1 ≤ N ≤ 50，
0 ≤ K ≤ N，
-1000 ≤ xi, yi , Xi , Yi ≤ 1000。
Source
二分答案+二分图最大匹配
二分一个答案，然后把小于等于这个距离的点对连边，做二分图最大匹配，这样可以找到最小值；
二分一个答案，然后把大于等于这个距离的点对连边，做二分图最大匹配，这样可以找到最大值。
#include <cmath>
#include <cstdio>
#include <cstring> const int mxn = ; const double eps = 1E-; int n, m; struct point
{
double x, y; inline void read(void)
{
scanf("%lf%lf", &x, &y);
}
}A[mxn], B[mxn]; inline double sqr(double x)
{
return x * x;
} inline double dis(const point &a, const point &b)
{
return sqr(a.x - b.x) + sqr(a.y - b.y);
} int mat[mxn];
int vis[mxn]; bool G[mxn][mxn]; bool dfs(int u)
{
for (int i = ; i <= n; ++i)
if (G[u][i] && !vis[i])
{
vis[i] = true; if (!mat[i] || dfs(mat[i]))
return mat[i] = u, true;
} return false;
} inline int calc(void)
{
int ret = ; memset(mat, , sizeof mat); for (int i = ; i <= n; ++i)
if (memset(vis, , sizeof vis), dfs(i))++ret; return ret;
} namespace solve1
{
inline void build(double k)
{
memset(G, , sizeof G); for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
if (dis(A[i], B[j]) <= k)
G[i][j] = true;
} inline void main(void)
{
double lt = , rt = 1E7, mid, ans = 1E7; while (lt + eps <= rt)
{
mid = (lt + rt) / ; build(mid); if (calc() >= m)
rt = mid - eps, ans = mid;
else
lt = mid + eps;
} printf("%.2lf ", sqrt(ans));
}
} namespace solve2
{
inline void build(double k)
{
memset(G, , sizeof G); for (int i = ; i <= n; ++i)
for (int j = ; j <= n; ++j)
if (dis(A[i], B[j]) >= k)
G[i][j] = true;
} inline void main(void)
{
if (n == m)
puts("+INF");
else
{
double lt = , rt = 1E7, mid, ans = 1E7; while (lt + eps <= rt)
{
mid = (lt + rt) / ; build(mid); if (calc() >= n - m)
lt = mid + eps, ans = mid;
else
rt = mid - eps;
} printf("%.2lf\n", sqrt(ans));
}
}
} signed main(void)
{
scanf("%d%d", &n, &m); for (int i = ; i <= n; ++i)
A[i].read(); for (int i = ; i <= n; ++i)
B[i].read(); solve1::main();
solve2::main();
}
@Author: YouSiki