fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. vector<int> gph[150];
  4. int seen[150];
  5. int match[150];
  6. bool dfs(int u)
  7. {
  8.     for(int i=0;i<gph[u].size();i++)
  9.     {
  10.         int v=gph[u][i];
  11.         if(!seen[v])
  12.         {
  13.             seen[v]=true;
  14.             if(match[v]<0 or dfs(match[v]))
  15.             {
  16.                 match[v]=u;
  17.                 return true;
  18.             }
  19.         }
  20.     }
  21.     return false;
  22. }
  23. struct ss
  24. {
  25.     double x,y;
  26. };
  27. int main()
  28. {
  29.         int t,n,i,m,j;
  30.         struct ss a[109],b[109];
  31.         double s,v,d,x,y;
  32.         cin>>n>>m>>s>>v;
  33.         for(i=0;i<=122;i++)
  34.             match[i]=-1;
  35.         for(i=1;i<=n;i++)
  36.         {
  37.             cin>>x>>y;
  38.             a[i].x=x;
  39.             a[i].y=y;
  40.         }
  41.         for(i=1;i<=m;i++)
  42.         {
  43.             cin>>x>>y;
  44.             b[i].x=x;
  45.             b[i].y=y;
  46.         }
  47.         for(i=1;i<=n;i++)
  48.         {
  49.             for(j=1;j<=m;j++)
  50.             {
  51.                 d=sqrt((a[i].x-b[j].x)*(a[i].x-b[j].x)+(a[i].y-b[j].y)*(a[i].y-b[j].y));
  52.                 d=d/v;
  53.                 if(d<=s)
  54.                 {
  55.                     gph[i].push_back(j);
  56.                 }
  57.             }
  58.         }
  59.         int result=0;
  60.         for(i=1;i<=n;i++)
  61.         {
  62.             memset(seen,0,sizeof(seen));
  63.             if(dfs(i))
  64.                 result++;
  65.         }
  66.         cout<<n-result<<endl;
  67.         return 0;
  68. }
  69.  
Success #stdin #stdout 0s 3236KB
comments (?)
stdin
copy 
2 2 5 10
1.0 1.0
2.0 2.0
100.0 100.0
20.0 20.0
stdout
copy 
1
https://ideone.com/vWyz2o
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!