fork(1) download
  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 3280KB
stdin
3 4 5 10
1.0 1.0
2.0 2.0
3.0 3.0
100.0 100.0
20.0 20.0
30.0 30.0
53.0 3.0
stdout
1