No.620 ぐるぐるぐるりん

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 11
作問者 : はむこはむこ / テスター : uwiuwi
1 ProblemId : 2023 / 出題時の順位表
問題文最終更新日: 2018-08-23 23:20:41

問題文

あなたは今、渦巻く海の中で漂流しています。
ちょうど時刻$T$で救助船が座標$(g_x, g_y)$に現れることを知っているので、そこまでなんとか泳ごうとしています。
時刻$t=T$以外の時刻では、座標$(g_x, g_y)$に自分がいたとしても救助船はそこにいないので、救助船に乗ることはできません。

今、あなたは時刻$t=0$で座標$(1, 0)$にいます。
時刻$t$で位置$(x_t, y_t)$にいるときに、そこから$1$秒間力$(u_{x, t}, u_{y, t})$で泳ぐことによって、位置$(x_{t+1}, y_{t+1})$に移動することができます。
渦の回転速度$\omega$と、渦の中心座標$(0, 0)$から外に流される速度$v$は事前にわかっています。
これらの速度によって、時刻$t+1$での座標は以下のように計算できます。
$x_{t+1} = x_t - y_t \omega + x_t v + u_{x, t}$
$y_{t+1} = y_t + x_t \omega + y_t v + u_{y, t}$

以下の動画は、$\omega = 0.3, v = 0.01$の海で全く力をかけなかった(つまり$u_{x, t} = u_{y, t}=0$)時に流される様子です。

あなたは体力が$p$しか残っていないので、あまり多くの力を出し続けることができません。
具体的には、$\displaystyle \sum_{0\le t < T}(u_{x, t}^2 + u_{y, t}^2) < p$を満たさなければ、救助船にたどり着く前に力尽きてしまいます。

$n$種類の、様々な渦の強さ・救助船の出現時刻・救助船の出現位置について、
力尽きずに救助船まで移動できるような、力のかけかたを1例ずつ、計算してください。

入力

n
T p omega v g_x g_y
...
T p omega v g_x g_y

$1 \le n \le 1000$
$1 \le T \le 15$, 整数
$0 \le p \le 10^9$, 小数
$-3 \le \omega, v \le 3$, 小数
$-100 \le g_x, g_y \le 100$, 小数

小数入力は小数点以下第4位まで与えられる(小数点以下第5位以降は入力されない)。
力尽きずに救助船に移動できることが保証される。
各ケースについて$p$は、Writerが見つけた$u_{x, t}, u_{y, t}$の二乗和の$101$ %以上である。

出力

各ケースで、そのケースにおける$u_{x, t}, u_{y, t}$を$T$行ずつ出力してください。
$t$行目($0\le t < T$)には、$t\sim t+1$秒の間にかける力$u_{x, t}, u_{y, t}$をスペース区切りで出力してください。
$(x_T, y_T)$と$(g_x, g_y)$とのユークリッド距離が$10^{-4}$以下である必要がある。
$\displaystyle \sum_{0\le t < T} (u_{x, t}^2 + u_{y, t}^2) < p$である必要がある。
最後に改行してください。

サンプル

サンプル1
入力
1
5 5.5 0.5 -0.5 -1.125 2.125
出力
1 0
1 0
1 0
0 1
0 1

初め、$(x_0, y_0) = (1, 0)$です。
$x_1 = x_0 - y_0 \cdot 0.5 + x_0 \cdot (-0.5) + 1 = 1.5$
$y_1 = y_0 + x_0 \cdot 0.5 + y_0 \cdot (-0.5) + 0 = 0.5$
$x_2 = x_1 - y_1 \cdot 0.5 + x_1 \cdot (-0.5) + 1 = 1.5$
$y_2 = y_1 + x_1 \cdot 0.5 + y_1 \cdot (-0.5) + 0 = 1$
$x_3 = x_2 - y_2 \cdot 0.5 + x_2 \cdot (-0.5) + 1 = 1.25$
$y_3 = y_2 + x_2 \cdot 0.5 + y_2 \cdot (-0.5) + 0 = 1.25$
$x_4 = x_3 - y_3 \cdot 0.5 + x_3 \cdot (-0.5) + 0 = 0$
$y_4 = y_3 + x_3 \cdot 0.5 + y_3 \cdot (-0.5) + 1 = 2.25$
$x_5 = x_4 - y_4 \cdot 0.5 + x_4 \cdot (-0.5) + 0 = -1.125$
$y_5 = y_4 + x_4 \cdot 0.5 + y_4 \cdot (-0.5) + 1 = 2.125$


力$\sum_{0\le t < T} (u_{x, t}^2 + u_{y, t}^2) = 5 < 5.5$なので、力尽きずに、ちょうど時刻$T=5$で$(-1.125, 2.125)$に移動できました。
ここで、ちょうど時刻$T$であることに注意してください。
つまり、たとえ時刻$t < T$で救助船に着いたとしても、ちょうど時刻$t=T$で別の場所に移動していたら救助されません。

サンプル2
入力
1
15 10 0.9 0.1 1 0
出力
-0.5590832663553096838087753950308211869924 -0.4538251666614241209630250389883698858284
-0.1022519519779994767825093832103178215220 -0.4962290213105669546263341157521509217077
0.1654103821800548689447286215825627664344 -0.3157815248622887024281327694730236999021
0.2307696993931288061689026738787511305873 -0.0982625412804297967609258937504712605460
0.1694470081608061894849455789047176779150 0.0493088782402688876135453052707013910094
0.0703038210696261387682489546469000174511 0.1023475610935749273856364832679943788207
-0.0073161395087270862120910853640398663345 0.0870573050324732387750411265192607146446
-0.0427719445489236518612402408734407543989 0.0441477772167654059713281372578919103944
-0.0429614547024281751287882839818177416191 0.0049840618041635591964723991237340428029
-0.0256154731665434461238743755334690277436 -0.0164271491324782774210512591508970281495
-0.0066299931999826736638264240708551255921 -0.0203583118295128558297550375871809436035
0.0054601426369248197322989711588459016411 -0.0140401667784384298875424365582453845036
0.0092288648520925917442445617078217168228 -0.0052128985559520393583323588648781310440
0.0073481980384297593332336429039486347392 0.0012731633443131396118876835776845268811
0.0034342430857618008364050277148038503583 0.0039672563676555400234528814262802143276

力$\sum_{0\le t < T} (u_{x, t}^2 + u_{y, t}^2) = 1.0268684859$なので、余力$10.0$より小さい力で救助船にちょうどたどり着くことができます。

ぐるぐるぐるりん。

サンプル3
入力
4
6 9770 0.1359 -0.1674 -3.4238 90.2458
8 4359 -2.9435 -2.7331 -33.5567 72.6887
1 8317 1.4861 -1.0168 72.7476 -5.3280
7 4249 1.0773 2.4532 4.1420 -4.4472
出力
8.8610640622215729803046180279579857597128 9.1624287318977981637441176943070786364842
8.6168617587290694441806704340081068949075 12.4110740390427459851549474301179998292355
7.7108320088957468634027758724869272555225 16.1649965278016668635691077682281502347905
5.9340532901000440243154121500168685088283 20.3836588637009756136420079997151333373040
3.0498513981872338589503013128734210113180 24.9797425758913909030201061511888838140294
-1.2019824014747570554983990831487972172908 29.8059009880592431125656549539826301042922
1.5774550919225495036963061168400201950135 2.6797588212359079336537942550577895417518
0.4417259778202559507916287462325755086567 -0.7959946947792882938096763190127802545248
-0.2664219693281557105779717986582255662142 0.0067980082291050485892578748598619187149
0.0412883921536529575847460082904660794156 0.0662018199037403666051913170287335219655
0.0105682176601090039463372305394983641236 -0.0202494208188849568767417319570256495354
-0.0066781880176901074579187689295167729142 0.0003416850665363352444053868239848270605
0.0010781542029716321279275703659550345037 0.0016339864000407908900536213536724972073
0.0002520679471596301568503406542731681839 -0.0005146947256041561891137803286255802959
72.7643999272356000740380466140777571126819 -6.8140999931859000064010567498939963115845
-3.1914891398354974239026660143281333148479 -0.9961849458246479833869839459747907994824
-0.7602242579764328366540362957870513582748 -0.5256499881103495447451541544570119413038
-0.1573479273710753174257259007218223700875 -0.2013091944478191229884848911790840020331
-0.0249506562886531407013317000742613771536 -0.0660803128887944921782387347475307137756
-0.0011441418288945185628463670213239566920 -0.0194929042282700865605649109824071274488
0.0013029071067033701106056831076074331577 -0.0052384114450990508244504484380854592018
0.0007751175941197825311479441268147638766 -0.0012751587134330459073761065980079365545

それぞれのケースについて$6, 8, 1, 7$行出力するので、合計で$22$行出力することになる。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。