1576.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1576 on 2006-01-03 at 21:02:11 */ 
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

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

int x[MAX], y[MAX];
double le[MAX], ri[MAX];
bool climb[MAX][MAX], check[MAX];
int match[MAX], n;

class Person {
private:
	double f(double, double, double) const;
public:
	double c, w, s;
	void make();
	double cost(int) const;
};
double Person::f(double x, double y, double p) const {
	return fabs(s-p)/w + sqrt((p-x)*(p-x)+y*y)/c;
}
void Person::make() {
	scanf("%lf %lf %lf", &c, &w, &s);
}
double Person::cost(int o) const {
	double p = s;
	if(s > x[o]) p = min(p, x[o]+c*y[o]/sqrt(w*w-c*c));
	else p = max(p, x[o]-c*y[o]/sqrt(w*w-c*c));
	int p1 = (int)floor(p), p2 = p1+1;
	if(f(x[o], y[o], p1) < f(x[o], y[o], p2)) p = p1;
	else p = p2;
	if(p < le[o-1]) p = ceil(le[o-1]);
	else if(p > ri[o-1]) p = floor(ri[o-1]);
	return f(x[o], y[o], p);
}

bool Perfect_Match();
bool DFS(int);

int main()
{
	Person p[MAX];
	double h, l, d[MAX][MAX];
	int i, j;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n+2; i++) scanf("%d %d", &x[i], &y[i]);
		for(i = 0; i < n; i++) p[i].make();
		for(i = 0; i < n; i++) {
			le[i] = 0; ri[i] = x[n+1];
			for(j = 0; j < n+2; j++) {
				if(y[j] < y[i+1]) {
					double m = (double)(x[j]*y[i+1]-x[i+1]*y[j]) / (y[i+1]-y[j]);
					if(j < i+1) le[i] = max(le[i], m);
					else ri[i] = min(ri[i], m);
				}
			}
		}
		h = 0; l = INF;
		for(i = 0; i < n; i++) {
			for(j = 0; j < n; j++) {
				d[i][j] = p[i].cost(j+1);
				h = max(h, d[i][j]); l = min(l, d[i][j]);
			}
		}
		while(h - l > 0.005) {
			double mid = (h + l) / 2;
			for(i = 0; i < n; i++) {
				for(j = 0; j < n; j++) {
					if(d[i][j] - mid < eps) climb[i][j] = true;
					else climb[i][j] = false;
				}
			}
			if(Perfect_Match()) h = mid;
			else l = mid;
		}
		printf("%.2lf\n", (h-0.004));
	}
	
	return 0;
}

bool Perfect_Match()
{
	int i;
	memset(match, -1, sizeof(match));
	for(i = 0; i < n; i++) {
		memset(check, false, sizeof(check));
		if(!DFS(i)) return false;
	}
	return true;
}
bool DFS(int p)
{
	int i;
	for(i = 0; i < n; i++) {
		if(!check[i] && climb[i][p]) {
			check[i] = true;
			int t = match[i];
			match[i] = p;
			if(t == -1 || DFS(t)) return true;
			else match[i] = t;
		}
	}
	return false;
}