Earth Observation with a Mobile Robot Team

時間制限 : 5 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem E: Earth Observation with a Mobile Robot Team

地球環境観測用の新型移動ロボットが開発された. このロボットは,地面の上を動き回りながら,高性能センサーを用いてさまざまな観測データを収集する. また,近距離無線通信機能も備えており,近くのロボットとの間で観測データを交換することもできる. 自身の観測データや他のロボットから受信したデータを記憶しておくための大容量記憶装置も装備されている.

図1は,3台のロボットA, B, Cの位置とその電波が到達する範囲を図示したものである. 各円の中心がロボットの位置で,円の内側には電波が到達する. この図では,ロボットAとロボットBが,お互いに通信可能な位置におり,ロボットAからロボットB(およびその逆向き)に観測データを伝えることができる. 一方,ロボットCは離れた場所にいるため,ロボットAやロボットBと通信することはできない. しかし,図2のようにロボットBが移動してロボットCに接近すれば,ロボットBとロボットCの間で通信が可能となる. このようにして,ロボットAの観測データをロボットBが中継してロボットCに伝えることができる. 別の例として,図3のような配置の場合には,一瞬で多くのロボットにデータが伝わる.

図1: 3台のロボットの初期配置
図2: ロボットの移動による中継
図3: 複数ロボット間での一瞬の中継

以上の例からわかるように,ロボットがうまく移動すれば,観測データを短時間で多くのロボットに伝えることができる. あなたの仕事は,与えられたロボットの移動経路から,ロボット間で観測データがどのように伝わっていくかシミュレートするプログラムを作成することである. データのサイズにかかわらず,通信に要する時間は無視できると仮定すること.

Input

入力は複数のデータセットから構成され,各データセットは以下のような形式で与えられる.

N T R
ロボット1のニックネームと移動経路
ロボット2のニックネームと移動経路
...
ロボットNのニックネームと移動経路

N, T, R は 1 <=N <= 100, 1 <= T <= 1000, 1 <= R <= 10 を満たす整数であり,それぞれ,ロボットの台数,シミュレーション時間の上限,ロボットの電波が届く最大距離を表す.

各ロボットのニックネームと移動経路は以下のような形式で与えられる.

nickname
t0 x0 y0
t1 vx1 vy1
t2 vx2 vy2
...
tk vxk vyk

nickname は1文字以上8文字以下の英小文字の列であり,2台以上のロボットが同じニックネームを持つことはない. 残りはすべて整数であり,以下の条件を満たす.

0 = t0 < t1 < ... < tk = T
-10 <= vx1, vy1, ..., vxk, vyk<= 10

ロボットは2次元平面上を移動する. (x0, y0) は時刻 0 のロボットの位置である. 時刻 ti-1 から ti の間(ただ し,0 < i <= k),x 軸方向と y 軸方向に,それぞれ,速度 vxivyi でロボットは移動する. したがって,ロボットの軌跡は,2次元平面上の折れ線になる. なお,この折れ線は,自分自身と重なったり交差したりするかもしれない.

任意のデータセットが以下の条件を満たすと仮定してよい.

  • 時刻 0 には,どの2台のロボット間の距離もちょうど R にはならない.
  • ロボットの位置の x, y 座標は,常に-500以上,500以下の範囲に収まっている.
  • 2台のロボットが距離 R + 10-6 まで接近した場合には,その速度を保ったまま R - 10-6 以内まで接近する.
  • 2台のロボットが距離 R - 10-6 まで離れた場合には,その速度を保ったまま R + 10-6 以遠まで離れる.
  • 時刻 t にある2台のロボットがちょうど距離 R まで接近し,時刻 t' に2台のロボット(前述のものと1台または2台が同じでもよい)がちょうど R まで離れたとすると,tt' は,少なくとも 10-6 単位時間離れている(すなわち,|t - t' | >= 10-6).

なお,複数のロボットが,同一時刻に同じ位置に存在するようなデータが入力 に含まれる可能性もある. そのような場合にも,ロボットは決められた速度で移動を続けることができる と仮定してプログラムを作成しなさい.

入力の終わりは 0 0 0 で表される.

Output

ロボット1は,時刻 0 に取得した観測データを,他のすべてのロボットに伝えようとする. 入力の各データセットに対して, その観測データが,時刻 T までに実際に伝達されるすべてのロボットのニックネームを,1行に一つずつ辞書式順序で出力しなさい. ニックネームの前後に空白のような余分な文字を含まないこと. ロボット1のニックネームは,必ず出力に含まれなければならないことに注意.

Sample Input

3 5 10
red
0 0 0
5 0 0
green
0 5 5
5 6 1
blue
0 40 5
5 0 0
3 10 5
atom
0 47 32
5 -10 -7
10 1 0
pluto
0 0 0
7 0 0
10 3 3
gesicht
0 25 7
5 -7 -2
10 -1 10
4 100 7
impulse
0 -500 0
100 10 1
freedom
0 -491 0
100 9 2
destiny
0 -472 0
100 7 4
strike
0 -482 0
100 8 3
0 0 0

Output for the Sample Input

blue
green
red
atom
gesicht
pluto
freedom
impulse
strike

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2005-07-01
http://www2.teu.ac.jp/icpc/