【BZOJ2663】灵魂宝石 [二分]

  1 #include<iostream>  
  2 #include<algorithm>  
  3 #include<cstdio>  
  4 #include<cstring>  
  5 #include<cstdlib>  
  6 #include<cmath>  
  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<r-0.001)
109         {
110             mid=(l+r)/2.0;
111             if(Check_first(mid)) r=mid;
112             else l=mid;
113         }
114         if(Check_first(l)) printf("%.2lf ",l);
115         else printf("%.2lf ",r);
116          
117          
118         l=0.0;  r=3500.0;
119          
120         while(l<r-0.001)
121         {
122             mid=(l+r)/2.0;
123             if(Check_second(mid)) r=mid;
124             else l=mid;
125         }
126          
127         double ans;
128         if(Check_second(r)) ans=r;
129         else ans=l;
130          
131         if(fabs(ans-3500.0)<=0.01) printf("+INF");
132         else printf("%.2lf",ans);
133 }