灵魂宝石
Time Limit: 5 Sec Memory Limit: 128 MB[][][]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。Main idea
有n个人匹配n个宝石，每个人和宝石有一个坐标，R为自己给定的值，如果在平面内人和宝石的距离<R则一定匹配，距离=R可取可不取，距离>R则一定无法取，求使得可以取到k个匹配的R的最小值和最大值。
Solution
求最小值最大值，想到了二分答案，然后我们可以直观地看出可以使用二分图匹配来进行求匹配问题，二分一个R，如果人和宝石的距离<=R则连边，判断是否可行，这样我们可以求出最小的R。
发现最大的R无法这么取，因为可能有距离=R的情况，所以我们反向思考，考虑枚举一个R，距离>=R的连边，判断是否有<n-k个无法匹配，则可以求得R的最大值。
Code
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 9 const int ONE=101; 10 11 int n,k; 12 double l,mid,r; 13 double x,y; 14 int vis[ONE]; 15 int f[ONE][ONE],my[ONE]; 16 double X[ONE],Y[ONE]; 17 double dist[ONE][ONE]; 18 19 int get() 20 { 21 int res,Q=1; char c; 22 while( (c=getchar())<48 || c>57) 23 if(c=='-')Q=-1; 24 if(Q) res=c-48; 25 while((c=getchar())>=48 && c<=57) 26 res=res*10+c-48; 27 return res*Q; 28 } 29 30 int find(int i) 31 { 32 for(int j=1;j<=n;j++) 33 { 34 if(f[i][j] && !vis[j]) 35 { 36 vis[j]=1; 37 if(!my[j] || find(my[j])) 38 { 39 my[j]=i; 40 return 1; 41 } 42 } 43 } 44 return 0; 45 } 46 47 double Getdis(double x1,double y1,double x2,double y2) 48 { 49 return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) ); 50 } 51 52 int Check_first(double x) 53 { 54 memset(my,0,sizeof(my)); 55 for(int i=1;i<=n;i++) 56 for(int j=1;j<=n;j++) 57 { 58 f[i][j]=(dist[i][j]<=x); 59 } 60 61 int Ans=0; 62 for(int i=1;i<=n;i++) 63 { 64 memset(vis,0,sizeof(vis)); 65 if(find(i)) Ans++; 66 } 67 68 return Ans>=k; 69 } 70 71 int Check_second(double x) 72 { 73 memset(my,0,sizeof(my)); 74 for(int i=1;i<=n;i++) 75 for(int j=1;j<=n;j++) 76 { 77 f[i][j]=(dist[i][j]>=x); 78 } 79 80 int Ans=0; 81 for(int i=1;i<=n;i++) 82 { 83 memset(vis,0,sizeof(vis)); 84 if(find(i)) Ans++; 85 } 86 87 return Ans<=n-k-1; 88 } 89 90 int main() 91 { 92 n=get(); k=get(); 93 for(int i=1;i<=n;i++) 94 { 95 scanf("%lf %lf",&X[i],&Y[i]); 96 } 97 98 for(int i=1;i<=n;i++) 99 {100 scanf("%lf %lf",&x,&y);101 for(int j=1;j<=n;j++)102 dist[j][i]=Getdis(X[j],Y[j],x,y);103 }104 105 106 l=0.0; r=3500.0;107 108 while(l