fork download
copy 
  1. // There is nothing in a caterpillar that tells you its going to be a butterfly --------------------- !
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define rep(i,n) for(int i=0;i<n;i++)
  5. #define ll  long long int
  6. #define pi pair<ll,ll>
  7. #define pii pair<ll,pi>
  8. #define f first
  9. #define mp make_pair
  10. #define mod 1000000007
  11. #define s second
  12. #define pb push_back
  13. pi cats[211];
  14. pi mouse[211];
  15. int N,K;
  16. vector<int>g[211];
  17. double dist(int i,int j){
  18.     double ret=(cats[i].f-mouse[j].f)*(cats[i].f-mouse[j].f)+(cats[i].s-mouse[j].s)*(cats[i].s-mouse[j].s);
  19.     ret=sqrt(ret);
  20.     return ret;
  21. }
  22. int match[211];
  23. int seen[211];
  24. bool bpm(int p){
  25.     for(auto x:g[p]){
  26.         if(!seen[x]){
  27.             seen[x]=1;
  28.             if(match[x]==-1 or bpm(match[x])){
  29.                 match[x]=p;
  30.                 return 1;
  31.             }
  32.         }
  33.     }
  34.     return 0;
  35. }
  36. int maxBPM(){
  37.     int ans=0;
  38.     rep(i,N) match[i]=-1;
  39.     rep(i,N){
  40.         rep(j,N) seen[j]=0;
  41.         if(bpm(i)) ans++;
  42.     }
  43.     return ans;
  44. }
  45. bool ok(double x){
  46.     rep(i,N) g[i].clear();
  47.     rep(i,N){
  48.         rep(j,N){
  49.             if(dist(i,j)>x){
  50.                 g[i].pb(j);
  51.             }
  52.         }
  53.     }
  54.     int M=maxBPM();
  55.     if(2*N-M>=K) return 1;
  56.     return 0;
  57. }
  58. int main(){
  59.     cin >> N >> K;
  60.     rep(i,N){
  61.         cin >> cats[i].f >> cats[i].s;
  62.     }
  63.     rep(i,N){
  64.         cin >> mouse[i].f >> mouse[i].s;
  65.     }
  66.     double lo=0;
  67.     double hi=1e14;
  68.     double mid;
  69.     rep(itr,200){
  70.         mid=(hi+lo)/2.0;
  71.         if(ok(mid)) hi=mid;
  72.         else lo=mid;
  73.     }
  74.    printf("%.7f",hi);
  75. }
Success #stdin #stdout 0s 3476KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000
https://ideone.com/QazzDu
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!