問題一覧 > 通常問題

No.2179 Planet Traveler

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : MasKoaTSMasKoaTS / テスター : taiga0629kyoprotaiga0629kyopro potato167potato167
0 ProblemId : 8306 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-28 21:07:37

問題文

二次元平面上の宇宙に $1$ 個の恒星と $1,2,\dots,N$ の番号が付いた $N$ 個の惑星があります。

恒星は常に座標 $(0,0)$ にありますが、惑星 $i$ $(1 \leq i \leq N)$ は最初座標 $(X_{i}, Y_{i})$ に位置し、
$T_{i}$ 年ごとに反時計回りに一回転する角速度で、先の恒星を中心とした半径・角速度一定の円運動を行います。
ただし、異なる $2$ 個の惑星が同じ座標となった場合でも衝突は起きず、上記の軌道は変化しないものとします。

魔法使いのコアさんの目的は、転移魔法を使い、$0$ 個以上の惑星を経由して惑星 $1$ から惑星 $N$ へ移動することです。

コアさんの魔法レベルは整数 $s$ で表され、最初 $s=0$ です。コアさんが訓練を $1$ 回行う度に $s$ は $1$ 増加します。
そして、次の条件を満たす場合に限り、コアさんは惑星 $i$ から惑星 $j$ $(1 \leq i,j \leq N \text{かつ} i \neq j)$ に直接移動できます。

  • 惑星 $i, j$ 間のユークリッド距離の取り得る最小値が $\sqrt{s}$ 以下である。

  • > 「ユークリッド距離」の定義(クリックで展開)

    二次元平面上の任意の $2$ 点 $P_{1} ( x_{1}, y_{1} )$, $P_{2} ( x_{2}, y_{2} )$ について、
    これら $2$ 点間のユークリッド距離 $L^{2} (P_{1}, P_{2} )$ は次のように定義されます。

    • $L^{2} (P_{1}, P_{2} ) := \sqrt{ (x_{1}-x_{2})^{2} + (y_{1}-y_{2})^{2} } $

コアさんが先の目的を達成するためには、最小で何回の訓練を行う必要がありますか?

制約

  • $2 \leq N \leq 800$

  • $-2 \times 10^{4} \leq X_{i}, Y_{i} \leq 2 \times 10^{4}$ $(1 \leq i \leq N)$

  • $(X_{i}, Y_{i}) \neq (0, 0)$ $(1 \leq i \leq N)$

  • $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq N)$

  • $1 \leq T_{i} \leq 10^{9}$ $(1 \leq i \leq N)$

  • 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$
$X_{1}$ $Y_{1}$ $T_{1}$
$X_{2}$ $Y_{2}$ $T_{2}$
     $\vdots$
$X_{N}$ $Y_{N}$ $T_{N}$
  • $1$ 行目には $N$ が与えられる

  • $(1 + i)$ $(1 \leq i \leq N)$ 行目には $X_{i}, Y_{i}, T_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

サンプル1
入力
3
1 1 3
0 3 4
-5 -5 3
出力
17

例えば、次のような移動経路を考えれば良いです。

  1. 惑星 $1$ → 惑星 $2$

  2. 惑星 $2$ → 惑星 $3$

このとき、最初の状態からの経過年数を $t$ とすると、惑星 $1,2$ 間のユークリッド距離の最小値 $d_{1}$ は

  $\displaystyle d_{1} = 3 - \sqrt{2}$ $\left( \text{例えば } t=\dfrac{3}{2} \text{ のとき} \right)$

惑星 $2,3$ 間のユークリッド距離の最小値 $d_{2}$ は

  $\displaystyle d_{2} = 5 \sqrt{2} - 3$ $\left( \text{例えば } t=\dfrac{15}{2} \text{ のとき} \right)$

であり、

  $\displaystyle \max(d_{1}, d_{2}) = 5 \sqrt{2} - 3 \approx 4.07$

なので、上の経路を採用する場合、$s$ は $17$ 以上である必要があります。

$s < 17$ のとき、惑星 $1$ から惑星 $3$ への移動経路は存在しません。

サンプル2
入力
4
10 10 100
-1 -1 100
-5 -5 100
3 3 100
出力
98

惑星 $1$ から惑星 $4$ に直接移動すれば良いです。

必ずしもすべての惑星を経由する必要はありません。

サンプル3
入力
2
4 3 2
-5 0 5
出力
0

ある実数 $t_{0}$ が存在し、最初の状態から $t_{0}$ 年経過後に
異なる $2$ 個の惑星の座標が等しくなることもあります。

サンプル4
入力
2
20000 20000 1000000000
-20000 -20000 1000000000
出力
3200000000

答えは32bit整数型に収まらない可能性があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。