pku2536.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>
#include <string.h>
#define SIZE 110
typedef struct 
{
	double x, y;
} Point;

Point H[SIZE], G[SIZE];
int st[SIZE][SIZE];
int chk[SIZE];
int match[SIZE];
int N, M, s, v;
double maxd;

int Check(int i, int j)
{
	if ((G[i].x - H[j].x) * (G[i].x - H[j].x) + (G[i].y - H[j].y) * (G[i].y - H[j].y) < maxd)
	{
		return 1;
	}
	return 0;
}

int DFS(int p)
{
	int i, t;
	for (i = 0; i < N; i++)
	{
		if (st[i][p] && !chk[i])
		{
			chk[i] = 1;
			t = match[i];
			match[i] = p;
			if (t == -1 || DFS(t))
			{
				return 1;
			}
			match[i] = t;
		}
	}
	return 0;
}

void Solve()
{
	int i, j, ans;
	maxd = s;
	maxd = maxd * v;
	maxd = maxd * maxd;
	for (i = 0; i < N; i++)
	{
		scanf("%lf %lf", &G[i].x, &G[i].y);
	}
	for (i = 0; i < M; i++)
	{
		scanf("%lf %lf", &H[i].x, &H[i].y);
	}
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			st[i][j] = Check(i, j);
		}
	}
	ans = 0;
	memset(match, -1, sizeof(match));
	for (i = 0; i < M; i++)
	{
		memset(chk, 0, sizeof(chk));
		ans += DFS(i);
	}
	printf("%d\n", N - ans);
}

int main()
{
	while (scanf("%d %d %d %d", &N, &M, &s, &v) != EOF)
	{
		Solve();
	}
	return 0;
}