AOJ 1139 Earth Observation with a Mobile Robot

問題

日本語なので本文参照（http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1139&lang=jp）

制約条件

入力は全て整数
n≦100

方針

ロボット同士の距離がRになるタイミングを全部列挙する。
そのタイミングでのデータの遷移を全部シミュレーションすればいい。

ロボット同士の距離がRになるタイミングは、
時間tにおけるそれぞれの折れ線上でのロボットの座標が、
(x0 + vx(t - t0), y0 + vy(t - t0))とかけることから、
ロボット同士の距離=Rという式はtに関する二次方程式になって、それを解けば出てくる。

線分同士を全部見るとさすがに間に合わないので、
尺取法で、必要な線分同士だけを見るようにする。

データの遷移は、union-findか何かを使って適当にマージすればいい。
割とやるだけ。

ソースコード

const int MX = 1010, SZ = 110;
ll n, T, r, x[SZ], y[SZ], sz[SZ], px[SZ][MX], py[SZ][MX];
ll t[SZ][MX], vx[SZ][MX], vy[SZ][MX];
string name[SZ];
double xs[SZ], ys[SZ];
bool ok[SZ];
int p[SZ];
inline int root(int x){ return x == p[x] ? x : (p[x] = root(p[x])); }

inline pair<double, double> solve(double a, double b, double c){
	if(a == 0){
		if(b == 0) return mp(INF, INF);
		return mp(-c / b, INF);
	}
	double D = b * b - 4 * a * c;
	if(D < 0) return mp(INF, INF);
	D = sqrt(D);
	return mp((-b + D) / (2 * a), (-b - D) / (2 * a));
}
inline double dist(double x, double y){
	return sqrt(x * x + y * y);
}

int main()
{
	while(1){
		cin >> n >> T >> r;
		if(n == 0) break;
		set<double> ts;
		rep(i, n){
			cin >> name[i];
			int k = 0;
			while(cin >> t[i][k] >> vx[i][k] >> vy[i][k]){
				ts.insert(t[i][k]);
				px[i][k] = k ? px[i][k - 1] + ll(t[i][k] - t[i][k - 1]) * vx[i][k] : vx[i][k];
				py[i][k] = k ? py[i][k - 1] + ll(t[i][k] - t[i][k - 1]) * vy[i][k] : vy[i][k];
				if(t[i][k++] == T) break;
			}
			sz[i] = k;
		}
		
		rep(i, n) rep(j, i){
			for(int a = 0, b = 0; a < sz[i] - 1 && b < sz[j] - 1; a++){
				while(b < sz[j] - 1 && t[i][a] > t[j][b + 1]) b++;
				for(; b < sz[j] - 1 && t[j][b] <= t[i][a + 1]; b++){
					double xa = px[i][a], ya = py[i][a], vxa = vx[i][a + 1], vya = vy[i][a + 1];
					double xb = px[j][b], yb = py[j][b], vxb = vx[j][b + 1], vyb = vy[j][b + 1];
					double dvx = vxa - vxb, dvy = vya - vyb;
					double dx = xa - xb - vxa * t[i][a] + vxb * t[j][b];
					double dy = ya - yb - vya * t[i][a] + vyb * t[j][b];
					pair<double, double> p = solve(dvx * dvx + dvy * dvy,
						2 * dvx * dx + 2 * dvy * dy, dx * dx + dy * dy - r * r);
					if(max(t[i][a], t[j][b]) - EPS < p.first  &&
						p.first  < min(t[i][a + 1], t[j][b + 1]) + EPS)
						ts.insert(p.first);
					if(max(t[i][a], t[j][b]) - EPS < p.second &&
						p.second < min(t[i][a + 1], t[j][b + 1]) + EPS)
						ts.insert(p.second);
					if(b + 1 == sz[j] - 1 || t[j][b + 1] > t[i][a + 1]) break;
				}
			}
		}
		memset(ok, 0, sizeof(ok));
		ok[0] = 1;
		fr(it, ts){
			double T = *it;
			
			rep(i, n){
				int j = lower_bound(t[i], t[i] + sz[i], T + EPS) - t[i] - 1;
				xs[i] = px[i][j] + vx[i][j + 1] * (T - t[i][j]);
				ys[i] = py[i][j] + vy[i][j + 1] * (T - t[i][j]);
			}
			
			rep(i, n) p[i] = i;
			rep(i, n) rep(j, i){
				if(dist(xs[i] - xs[j], ys[i] - ys[j]) < r + EPS){
					int a = root(i), b = root(j);
					if(a != b) p[a] = b;
				}
			}
			rep(i, n) if(ok[i]) rep(j, n) if(root(i) == root(j)) ok[j] = 1;
		}
		set<string> ans;
		rep(i, n) if(ok[i]) ans.insert(name[i]);
		fr(i, ans) cout << *i << endl;
	}
	return 0;
}