【BZOJ2663】灵魂宝石 [二分]

小灰灰 2021-03-28 15:26 425阅读 0赞

## 灵魂宝石 ##

Time Limit: 5 Sec  Memory Limit: 128 MB  
[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。

## Main idea ##

有n个人匹配n个宝石，每个人和宝石有一个坐标，R为自己给定的值，如果在平面内人和宝石的距离<R则一定匹配，距离=R可取可不取，距离>R则一定无法取，求使得可以取到k个匹配的R的最小值和最大值。

## Solution ##

求最小值最大值，想到了二分答案，然后我们可以直观地看出可以使用二分图匹配来进行求匹配问题，二分一个R，如果人和宝石的距离<=R则连边，判断是否可行，这样我们可以求出最小的R。

发现最大的R无法这么取，因为可能有距离=R的情况，所以我们**反向思考**，考虑枚举一个R，距离>=R的连边，判断是否有<n-k个无法匹配，则可以求得R的最大值。

## Code ##

#include<iostream>  
     #include<algorithm>  
     #include<cstdio>  
     #include<cstring>  
     #include<cstdlib>  
     #include<cmath>  
     using namespace std;  
          
     const int ONE=101;
      
     int n,k;
     double l,mid,r;
     double x,y;
     int vis[ONE];
     int f[ONE][ONE],my[ONE];
     double X[ONE],Y[ONE];
     double dist[ONE][ONE];
      
     int get() 
     { 
             int res,Q=1;    char c;
             while( (c=getchar())<48 || c>57)
             if(c=='-')Q=-1;
             if(Q) res=c-48; 
             while((c=getchar())>=48 && c<=57) 
             res=res*10+c-48; 
             return res*Q; 
     }
      
     int find(int i)
     {
             for(int j=1;j<=n;j++)
             {
                 if(f[i][j] && !vis[j])
                 {
                     vis[j]=1;
                     if(!my[j] || find(my[j]))
                     {
                         my[j]=i;
                         return 1;
                     }
                 }
             }
             return 0;
     }
      
     double Getdis(double x1,double y1,double x2,double y2)
     {
             return sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
     }
      
     int Check_first(double x)
     {
             memset(my,0,sizeof(my));
             for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
             {
                 f[i][j]=(dist[i][j]<=x); 
             }
              
             int Ans=0;
             for(int i=1;i<=n;i++)
             {
                 memset(vis,0,sizeof(vis));
                 if(find(i)) Ans++;
             }
              
             return Ans>=k;
     }
      
     int Check_second(double x)
     {
             memset(my,0,sizeof(my));
             for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
             {
                 f[i][j]=(dist[i][j]>=x); 
             }
              
             int Ans=0;
             for(int i=1;i<=n;i++)
             {
                 memset(vis,0,sizeof(vis));
                 if(find(i)) Ans++;
             }
              
             return Ans<=n-k-1;
     }
      
     int main()
     {
             n=get();    k=get();
             for(int i=1;i<=n;i++)
             {
                 scanf("%lf %lf",&X[i],&Y[i]);
             }
              
             for(int i=1;i<=n;i++)
             {
                 scanf("%lf %lf",&x,&y);
                 for(int j=1;j<=n;j++)
                 dist[j][i]=Getdis(X[j],Y[j],x,y);
             }
              
              
             l=0.0;  r=3500.0;
              
             while(l<r-0.001)
             {
                 mid=(l+r)/2.0;
                 if(Check_first(mid)) r=mid;
                 else l=mid;
             }
             if(Check_first(l)) printf("%.2lf ",l);
             else printf("%.2lf ",r);
              
              
             l=0.0;  r=3500.0;
              
             while(l<r-0.001)
             {
                 mid=(l+r)/2.0;
                 if(Check_second(mid)) r=mid;
                 else l=mid;
             }
              
             double ans;
             if(Check_second(r)) ans=r;
             else ans=l;
              
             if(fabs(ans-3500.0)<=0.01) printf("+INF");
             else printf("%.2lf",ans);
     }