2340.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2340 on 2006-08-25 at 17:06:18 */ 
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<double, double> pdd;
const int N = 320;
const double eps = 1e-5;

class SegTree {
private:
	void update();
public:
	SegTree *left, *right;
	int x, y, cnt, len;
	SegTree(int, int);
	~SegTree() { if(y-x != 1) { delete left; delete right; } }
	void insert(int, int);
};
SegTree::SegTree(int cx, int cy) : left(NULL), right(NULL), x(cx), y(cy), cnt(0), len(0) {
	if(y-x == 1) return;
	int mid = (y+x)/2;
	left = new SegTree(x, mid); right = new SegTree(mid, y);
}
void SegTree::update() {
	if(cnt) len = y-x;
	else if(y-x != 1) len = left->len+right->len;
}
void SegTree::insert(int sx, int sy) {
	if(sx <= x && sy >= y) cnt++;
	else if(y-x != 1) {
		if(sx < (x+y)/2) left->insert(sx, sy);
		if(sy >= (x+y)/2) right->insert(sx, sy);
	}
	update();
}

class Object {
public:
	int x, y;
	bool bomb;
	void make(bool b) { bomb = b; scanf("%d %d", &x, &y); }
	bool operator <(const Object& o) const { return y < o.y; }
	pdd zone(int, int, int) const;
};
pdd Object::zone(int xm, int vm, int vb) const {
	double a = 1.0*(xm-x)/vb-1.0*y/vm, b = 1.0*(xm-x+1)/vb-1.0*y/vm;
	a >?= 0;
	return pdd(a, b);
}

vector<int> g[N];
int match[N], check[N], n;
double x[N*4];

bool dfs(int, int);
bool cmp(double, double);
int disperse(double*, double*);

int main()
{
	int b, a, m, vb, va, vm, T;
	int mx[N];
	Object ob[N*2];

	scanf("%d", &T);
	for(int t = 1; t <= T; t++) {
		scanf("%d %d %d %d %d %d", &b, &a, &m, &vb, &va, &vm);
		n = max(b, m);
		for(int i = 0; i < n; i++) g[i].clear();
		for(int i = 0; i < b; i++) ob[i].make(true);
		for(int i = 0; i < a; i++) ob[i+b].make(false);
		for(int i = 0; i < m; i++) scanf("%d", &mx[i]);
		sort(ob, ob+a+b);
		for(int i = 0; i < m; i++) {
			int k = 0;
			for(int j = 0; j < a+b; j++) {
				pdd p = ob[j].zone(mx[i], vm, vb);
				if(p.second < -eps) continue;
				x[k++] = p.first; x[k++] = p.second;
			}
			int xn = disperse(x, x+k);
			SegTree st(0, xn);
			for(int j = 0, q = 0; j < a+b; j++) {
				pdd p = ob[j].zone(mx[i], vm, vb);
				if(p.second < -eps) continue;
				int x1 = lower_bound(x, x+xn, p.first, cmp)-x, x2 = lower_bound(x, x+xn, p.second, cmp)-x;
				int plen = st.len;
				st.insert(x1, x2);
				if(!ob[j].bomb) continue;
				else if(st.len != plen) g[i].push_back(q);
				q++;
			}
		}
		int mth = 0;
		memset(match, -1, sizeof(match)); memset(check, -1, sizeof(check));
		for(int i = 0; i < n; i++)
			if(dfs(i, i)) mth++;
		printf("Mission #%d: %d bomber(s) exploded\n", t, mth);
	}
	
	return 0;
}

bool cmp(double a, double b)
{
	if(fabs(a-b) < eps) return false;
	else return a < b;
}
int disperse(double* b, double* e)
{
	int n = e-b, dn = 1;
	sort(b, e);
	for(int i = 1; i < n; i++)
		if(fabs(b[i]-b[i-1]) > eps) b[dn++] = b[i];
	return dn;
}
bool dfs(int o, int k)
{
	for(int i = 0; i < g[o].size(); i++) {
		int mo = g[o][i];
		if(check[mo] == k) continue;
		check[mo] = k;
		int t = match[mo];
		match[mo] = o;
		if(t == -1 || dfs(t, k)) return true;
		match[mo] = t;
	}
	return false;
}