1851.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1851 on 2005-12-01 at 22:36:15 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;
const double eps = 1e-4;

class Point {
public:
	double x, y;
	static double distance(const Point&, const Point&);
	void init();
};
double Point::distance(const Point& p1, const Point& p2) {
	return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
void Point::init() {
	scanf("%lf %lf", &x, &y);
}

bool hide[MAX][MAX], check[MAX];
int match[MAX], n;

int DFS(int);

int main()
{
	int m, s, v, save;
	int i, j;
	Point gopher[MAX], hole[MAX];
	
	while(scanf("%d %d %d %d", &n, &m, &s, &v) == 4) {
		int ls = s * v * s * v;
		memset(hide, false, sizeof(hide));
		for(i = 0; i < n; i++) {
			gopher[i].init();
			match[i] = -1;
		}
		for(i = 0; i < m; i++) {
			hole[i].init();
		}
		for(i = 0; i < n; i++) {
			for(j = 0; j < m; j++) {
				if(Point::distance(gopher[i], hole[j]) - ls < eps) {
					hide[i][j] = true;
				}
			}
		}
		save = 0;
		for(i = 0; i < n; i++) {
			memset(check, false, sizeof(check));
			if(DFS(i)) {
				save++;
			}
		}
		printf("%d\n", n-save);
	}
	
	return 0;
}

int DFS(int p)
{
	int i, t;
	for(i = 0; i < n; i++) {
		if(hide[i][p] && !check[i]) {
			check[i] = true;
			t = match[i];
			match[i] = p;
			if(t == -1 || DFS(t)) {
				return 1;
			}
			match[i] = t;
		}
	}
	return 0;
}