2225.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2225 on 2006-05-15 at 20:15:10 */ 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

const int RM = 128;
const double INF = 1e8;

int n, T;

double near(int, int, int, int, int, double, double);
void spread(int, int);

class Robot {
public:
	char name[10];
	int o;
	vector<int> t, vx, vy;
	void make(int);
	double reach(Robot&, int, double) const;
	bool operator <(const Robot&) const;
};
void Robot::make(int co) {
	scanf("%s", name); o = co;
	t.clear(); vx.clear(); vy.clear();
	while(true) {
		int ct, cx, cy; scanf("%d %d %d", &ct, &cx, &cy);
		t.push_back(ct); vx.push_back(cx); vy.push_back(cy);
		if(ct == T) break;
	}
}
double Robot::reach(Robot& r, int R, double lmt) const {
	unsigned int a = 1, b = 1;
	int dx = vx[0]-r.vx[0], dy = vy[0]-r.vy[0];
	double ct = lmt, pt = 0;
	while(a < t.size() && b < r.t.size()) {
		double nt = min(t[a], r.t[b]);
		int dvx = vx[a]-r.vx[b], dvy = vy[a]-r.vy[b];
		if(nt >= lmt) {
			double vt = near(dx, dy, dvx, dvy, R, ct-pt, nt-pt);
			if(vt >= 0) return vt+pt;
			ct = nt;
		}
		dx += dvx*(nt-pt); dy += dvy*(nt-pt); pt = nt;
		if(t[a] < r.t[b]) a++;
		else if(t[a] > r.t[b]) b++;
		else a++, b++;
	}
	return INF;
}
bool Robot::operator <(const Robot& r) const {
	return strcmp(name, r.name) < 0;
}

Robot r[RM];

int main()
{
	int R, i, o;

	while(scanf("%d %d %d", &n, &T, &R) != EOF && n != 0) {
		for(i = 0; i < n; i++) r[i].make(i);
		sort(r, r+n);
		for(o = 0; r[o].o != 0; o++);
		spread(o, R);
	}
	
	return 0;
}

double near(int ca, int cc, int cb, int cd, int R, double t1, double t2)
{
	int a = cb*cb+cd*cd, b = 2*(ca*cb+cc*cd), c = ca*ca+cc*cc-R*R, delta = b*b-4*a*c;
	double f0 = a*t1*t1+b*t1+c;
	if(f0 <= 0) return t1;
	else if(a == 0 || delta < 0) return -1;
	else {
		double rs = sqrt(1.0*delta), rt = (-b-rs)/(2.0*a);
		if(rt <= t2 && rt >= t1) return rt;
		else return -1;
	}
}
void spread(int src, int R)
{
	bool vst[RM] = { false };
	double time[RM];
	int i;
	for(i = 0; i < n; i++) time[i] = INF;
	time[src] = 0;
	while(true) {
		double mint = INF; int mini;
		for(i = 0; i < n; i++)
			if(!vst[i] && mint > time[i]) { mint = time[i]; mini = i; }
		if(mint > T) break;
		vst[mini] = true;
		for(i = 0; i < n; i++)
			if(!vst[i]) time[i] = min(r[mini].reach(r[i], R, time[mini]), time[i]);
	}
	for(i = 0; i < n; i++)
		if(vst[i]) printf("%s\n", r[i].name);
}