No.2179 Planet Traveler
タグ : / 解いたユーザー数 71
作問者 :
MasKoaTS
/ テスター :
👑 
taiga0629kyopro
Problem Statement
In a universe on a two-dimensional plane, there are $1$ star and $N$ planets numbered $1,2,\dots,N$.
The star is always at coordinates $(0,0)$, while planet $i$ $(1 \leq i \leq N)$ is initially located at coordinates $(X_{i}, Y_{i})$, and,
with an angular velocity of one counterclockwise revolution every $T_{i}$ years, it moves in a circle of constant radius and constant angular velocity centered at the aforementioned star.
Even if $2$ different planets are at the same coordinates, no collision occurs and the orbits described above do not change.
The goal of the wizard Koa is to use teleportation magic to travel from planet $1$ to planet $N$, passing through $0$ or more planets.
Koa's magic level is represented by an integer $s$, and initially $s=0$. Each time Koa trains
$1$ time, $s$ increases by $1$.
Koa can move directly from planet $i$ to planet $j$
$(1 \leq i,j \leq N \text{ and } i \neq j)$ if and only if the following condition is satisfied.
The minimum possible value of the Euclidean distance between planets $i, j$ is at most $\sqrt{s}$.
$L^{2} (P_{1}, P_{2} ) := \sqrt{ (x_{1}-x_{2})^{2} + (y_{1}-y_{2})^{2} } $
Definition of "Euclidean distance" (click to expand)
For any $2$ points $P_{1} ( x_{1}, y_{1} )$, $P_{2} ( x_{2}, y_{2} )$ on a two-dimensional plane,
the Euclidean distance $L^{2} (P_{1}, P_{2} )$ between these $2$ points is defined as follows.
What is the minimum number of times Koa must train in order to achieve the goal above?
Constraints
$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)$
All input values are integers
Input
The input is given in the following format.
$N$
$X_{1}$ $Y_{1}$ $T_{1}$
$X_{2}$ $Y_{2}$ $T_{2}$
$\vdots$
$X_{N}$ $Y_{N}$ $T_{N}$
Line $1$ contains $N$
Line $(1 + i)$ $(1 \leq i \leq N)$ contains $X_{i}, Y_{i}, T_{i}$ in this order, separated by single-byte spaces
Output
Output the answer on $1$ line.
Sample
Sample 1
Input
3 1 1 3 0 3 4 -5 -5 3
Output
17
For example, consider the following route.
Planet $1$ → Planet $2$
Planet $2$ → Planet $3$
Here, letting $t$ be the number of years elapsed since the initial state, the minimum value $d_{1}$ of the Euclidean distance between planets $1,2$ is
$\displaystyle d_{1} = 3 - \sqrt{2}$ $\left( \text{for example, when } t=\dfrac{3}{2} \text{ holds} \right)$
the minimum value $d_{2}$ of the Euclidean distance between planets $2,3$ is
$\displaystyle d_{2} = 5 \sqrt{2} - 3$ $\left( \text{for example, when } t=\dfrac{15}{2} \text{ holds} \right)$
and
$\displaystyle \max(d_{1}, d_{2}) = 5 \sqrt{2} - 3 \approx 4.07$
so if the above route is adopted, $s$ must be at least $17$.
When $s < 17$, no route from planet $1$ to planet $3$ exists.
Sample 2
Input
4 10 10 100 -1 -1 100 -5 -5 100 3 3 100
Output
98
It suffices to move directly from planet $1$ to planet $4$.
It is not necessary to pass through all the planets.
Sample 3
Input
2 4 3 2 -5 0 5
Output
0
The coordinates of $2$ planets may coincide.
Sample 4
Input
2 20000 20000 1000000000 -20000 -20000 1000000000
Output
3200000000
The answer may not fit in a 32bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。