10080

#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";
	}
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *