prithivMLmods/Coder-Stat

1 2 3 4<h1>KND Warp</h1>5<h2>Problem</h2>6<p>KND君は会津大学に在籍する学生プログラマだ。彼はその優秀な頭脳をもってワープ装置を開発したことで有名である。ワープ装置とは便利なもので、ある場所から別の場所まで瞬時に移動することができる。彼はこれから地球上に点在するワープ装置を用いて様々な場所を可能な限り早くめぐる旅を計画している。</p>7<p>彼の隣人であるあなたの仕事は3次元空間 (xyz直交座標系) 上に存在する<var>N</var>個のワープ装置をうまく使用して、1から<var>M</var>までの番号がふられた<var>M</var>個の点を順に通って、<var>M</var>番目の点まで移動するときの最小の所要時間を求めることだ。はじめは1番目の点にいるものとし、どのワープ装置も任意のワープ装置へ時間0で移動できる。ワープ以外の単位距離の移動は単位時間を要する。経由点のクエリは<var>Q</var>個与えられる。</p>8 9<h2>Input</h2>10<p>11入力は複数のテストケースからなる。12ひとつのテストケースは以下の形式で与えられる。13入力の終わりを<var>N</var> = <var>Q</var> = 0のとき示す。14</p>15 16<pre>17<var>N</var> <var>Q</var>18<var>x<sub>1</sub></var> <var>y<sub>1</sub></var> <var>z<sub>1</sub></var>19<var>x<sub>2</sub></var> <var>y<sub>2</sub></var> <var>z<sub>2</sub></var>20...21<var>x<sub>N</sub></var> <var>y<sub>N</sub></var> <var>z<sub>N</sub></var>22<var>M<sub>1</sub></var>23<var>x<sub>1,1</sub></var> <var>y<sub>1,1</sub></var> <var>z<sub>1,1</sub></var>24<var>x<sub>1,2</sub></var> <var>y<sub>1,2</sub></var> <var>z<sub>1,2</sub></var>25...26<var>x<sub>1,M</sub></var> <var>y<sub>1,M</sub></var> <var>z<sub>1,M</sub></var>27 28<var>M<sub>2</sub></var>29<var>x<sub>2,1</sub></var> <var>y<sub>2,1</sub></var> <var>z<sub>2,1</sub></var>30<var>x<sub>2,2</sub></var> <var>y<sub>2,2</sub></var> <var>z<sub>2,2</sub></var>31...32<var>x<sub>2,M</sub></var> <var>y<sub>2,M</sub></var> <var>z<sub>2,M</sub></var>33...34<var>M<sub>Q</sub></var>35<var>x<sub>Q,1</sub></var> <var>y<sub>Q,1</sub></var> <var>z<sub>Q,1</sub></var>36<var>x<sub>Q,2</sub></var> <var>y<sub>Q,2</sub></var> <var>z<sub>Q,2</sub></var>37...38<var>x<sub>Q,M</sub></var> <var>y<sub>Q,M</sub></var> <var>z<sub>Q,M</sub></var>39</pre>40 41<p>42ここで、43</p>44<ul>45<li><var>N</var>:ワープ装置の数</li>46<li><var>Q</var>:旅のクエリの数</li>47<li><var>M<sub>i</sub></var>:i番目クエリの旅で訪れる点の数</li>48<li><var>x<sub>i,j</sub></var>,<var>y<sub>i,j</sub></var>,<var>z<sub>i,j</sub></var>:i番目のクエリの旅で訪れるj番目の点の座標(x,y,z)</li>49</ul>50<p>51である。52</p>53 54<h2>Constraints</h2>55<p>入力は以下の条件を満たす。</p>56<ul>57<li>テストケースの数は15個を超えない。</li>58<li>入力の半分程度は<var>N</var>&le;1000を満たす。</li>59<li>入力に含まれる値はすべて整数。</li>60<li>2&le;<var>N</var>&le;100,000</li>61<li>1&le;<var>Q</var>&le;1,000</li>62<li>2&le;<var>M</var>&le;100</li>63<li>-1,000,000&le;(全てのx,y,z座標値)&le;1,000,000</li>64<li>ワープ装置は上記の制約を満たす空間中にランダムに分布する(Sample Inputは例外)。</li>65<li>ワープ装置同士、中継点同士、ワープ装置と中継点はそれぞれ重なることがある。</li>66</ul>67 68<h2>Output</h2>69<p>各クエリにつき最小の所要時間を一行に出力せよ。この値はジャッジ出力の値と10<sup>-4</sup>より大きい差を持ってはならない。</p>70<h2>Sample Input</h2>71<pre>723 2730 0 0741 1 1752 2 276477-1 -1 -1783 3 379-1 -1 -1804 4 4812821234 5678 9012831716 6155 9455840 085</pre>86 87<h2>Sample Output</h2>88<pre>8912.12435565390810.00123456791</pre>92 93<h2>Notes</h2>94<p>入力ファイルのサイズは4MB程度になる。入力は高速にしたほうがよいが、たとえばC++であればcinでも十分である。</p>