1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> using namespace std; int gr[105][105]; int N,M; double S,V; struct point{ double x; double y; }; point goph[105],hole[105]; // A DFS based recursive function that returns true if a // matching for vertex u is possible bool bpm(int u, bool seen[], int matchR[]) { // Try every hole one by one for (int v = 0; v < M; v++) { // If gopher u can reach in hole v and v is // not occupied if (gr[u][v] && !seen[v]) { seen[v] = true; // Mark v as visited // If job 'v' is not assigned to a gopher OR // previously assigned gopher for hole v (which is matchR[v]) // has an alternate hole available. // Since v is marked as visited in the above line, matchR[v] // in the following recursive call will not get hole 'v' again if (matchR[v] < 0 || bpm(matchR[v], seen, matchR)) { matchR[v] = u; return true; } } } return false; } // Returns maximum number of matching from M to N int maxBPM() { // An array to keep track of the gophers assigned to // holes. The value of matchR[i] is the gopher number // assigned to hole i, the value -1 indicates nobody is // assigned. int matchR[M]; // Initially all holes are available memset(matchR, -1, sizeof(matchR)); int result = 0; // Count of holes assigned to gophers for (int u = 0; u < N; u++) { // Mark all holes as not seen for next gopher. bool seen[M]; memset(seen, 0, sizeof(seen)); // Find if the gopher 'u' can get a hole if (bpm(u, seen, matchR)) result++; } return result; } int main() { double a,b; double d,dist; while(scanf("%d%d%lf%lf",&N,&M,&S,&V)!=EOF)//n = gophr,m = hole { memset(gr,0,sizeof(gr)); dist = S*V; for(int i=0;i<N;i++) { cin>>a>>b; goph[i].x = a; goph[i].y = b; } for(int i=0;i<M;i++) { cin>>a>>b; hole[i].x = a; hole[i].y = b; } for(int i=0;i<N;i++) { for(int j=0;j<M;j++) { d = sqrt((goph[i].x-hole[j].x)*(goph[i].x-hole[j].x)+(goph[i].y-hole[j].y)*(goph[i].y-hole[j].y)); if(d<dist || (d-dist)<1e-7)//d<=dist gr[i][j] = 1; } } int mx = maxBPM(); cout<<N-mx<<"\n"; } } |