BZOJ 2663: [Beijing wc2012]灵魂宝石

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

2 1
1 0
4 0
0 0
4 4

Sample Output

1.00 5.00

HINT

对于100%的数据：

1 ≤ N ≤ 50，

0 ≤ K ≤ N，

-1000 ≤ xi, yi , Xi , Yi ≤ 1000。

Source

[Submit][Status][Discuss]

二分答案+二分图最大匹配

二分一个答案，然后把小于等于这个距离的点对连边，做二分图最大匹配，这样可以找到最小值；

二分一个答案，然后把大于等于这个距离的点对连边，做二分图最大匹配，这样可以找到最大值。

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 const int mxn = 55;
  6 
  7 const double eps = 1E-5;
  8 
  9 int n, m;
 10 
 11 struct point
 12 {
 13     double x, y;
 14     
 15     inline void read(void)
 16     {
 17         scanf("%lf%lf", &x, &y);
 18     }
 19 }A[mxn], B[mxn];
 20 
 21 inline double sqr(double x)
 22 {
 23     return x * x;
 24 }
 25 
 26 inline double dis(const point &a, const point &b)
 27 {
 28     return sqr(a.x - b.x) + sqr(a.y - b.y);
 29 }
 30 
 31 int mat[mxn];
 32 int vis[mxn];
 33 
 34 bool G[mxn][mxn];
 35 
 36 bool dfs(int u)
 37 {
 38     for (int i = 1; i <= n; ++i)
 39         if (G[u][i] && !vis[i])
 40         {
 41             vis[i] = true;
 42             
 43             if (!mat[i] || dfs(mat[i]))
 44                 return mat[i] = u, true;
 45         }
 46     
 47     return false;
 48 }
 49 
 50 inline int calc(void)
 51 {
 52     int ret = 0;
 53     
 54     memset(mat, 0, sizeof mat);
 55     
 56     for (int i = 1; i <= n; ++i)
 57         if (memset(vis, 0, sizeof vis), dfs(i))++ret;
 58     
 59     return ret;
 60 }
 61     
 62 namespace solve1
 63 {
 64     inline void build(double k)
 65     {
 66         memset(G, 0, sizeof G);
 67         
 68         for (int i = 1; i <= n; ++i)
 69             for (int j = 1; j <= n; ++j)
 70                 if (dis(A[i], B[j]) <= k)
 71                     G[i][j] = true;
 72     }
 73     
 74     inline void main(void)
 75     {
 76         double lt = 0, rt = 1E7, mid, ans = 1E7;
 77         
 78         while (lt + eps <= rt)
 79         {
 80             mid = (lt + rt) / 2;
 81             
 82             build(mid);
 83             
 84             if (calc() >= m)
 85                 rt = mid - eps, ans = mid;
 86             else
 87                 lt = mid + eps;
 88         }
 89         
 90         printf("%.2lf ", sqrt(ans));
 91     }
 92 }
 93 
 94 namespace solve2
 95 {
 96     inline void build(double k)
 97     {
 98         memset(G, 0, sizeof G);
 99         
100         for (int i = 1; i <= n; ++i)
101             for (int j = 1; j <= n; ++j)
102                 if (dis(A[i], B[j]) >= k)
103                     G[i][j] = true;
104     }
105     
106     inline void main(void)
107     {
108         if (n == m)
109             puts("+INF");
110         else
111         {
112             double lt = 0, rt = 1E7, mid, ans = 1E7;
113             
114             while (lt + eps <= rt)
115             {
116                 mid = (lt + rt) / 2;
117                 
118                 build(mid);
119                 
120                 if (calc() >= n - m)
121                     lt = mid + eps, ans = mid;
122                 else
123                     rt = mid - eps;
124             }
125             
126             printf("%.2lf
", sqrt(ans));
127         }
128     }
129 }
130 
131 signed main(void)
132 {
133     scanf("%d%d", &n, &m);
134     
135     for (int i = 1; i <= n; ++i)
136         A[i].read();
137     
138     for (int i = 1; i <= n; ++i)
139         B[i].read();
140     
141     solve1::main();
142     solve2::main();
143 }

@Author: YouSiki