問題一覧 > 通常問題

No.1599 Hikyaku

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 7.500秒 / メモリ制限 : 512 MB / 小数誤差許容問題 絶対誤差または相対誤差が $10^{-7}$ 以下。ただし、ジャッジ側の都合で500桁未満にしてください
タグ : (AC するまで非表示) / 解いたユーザー数 5
作問者 : e869120 / テスター : butsurizuki ygussany
お気に入りにしたユーザー ProblemId : 6421 / 自分の提出
問題文最終更新日: 2021-07-08 23:26:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
競プロ典型 90 問 期末試験 (順位表) の他の問題:

Problem Statement

The country of yuki is divided into a grid by $600$ roads running straight in the north-south direction and $600$ roads running straight in the east-west direction.
The intersection where the $i$-th $(1 \leq i \leq 600)$ north-south road from the west crosses the $j$-th $(1 \leq j \leq 600)$ east-west road from the south is denoted by $(i, j)$.
The distance between adjacent intersections, that is, between intersections $(p, q)$ and $(p+1, q)$ $[1 \leq p \leq 599, 1 \leq q \leq 600]$ or between intersections $(p, q)$ and $(p, q+1)$ $[1 \leq p \leq 600, 1 \leq q \leq 599]$, is $1000$.

There are $N$ postal carriers in the country of yuki, numbered $1, 2, \dots, N$. Currently, postal carrier $i$ is at intersection $(x_i, y_i)$.
Each postal carrier has a value called "speed"; the speed of postal carrier $i$ is $v_i$.
A postal carrier with speed $x$ can travel at a rate of distance $x$ per $1$ second.

Currently, postal carrier $1$ has a letter. How many seconds are required to deliver it to intersection $(X, Y)$?
Note that postal carriers who do not currently have the letter can also move.
Also, the time required to hand the letter to another postal carrier is negligible.

Input

$X$ $Y$
$N$
$x_1$ $y_1$ $v_1$
$x_2$ $y_2$ $v_2$
$x_3$ $y_3$ $v_3$
 $\vdots$
$x_N$ $y_N$ $v_N$

Output

Output the answer.
Your answer is considered correct if its absolute or relative error from the expected answer is at most $10^{-7}$.

Constraints

  • $1 \leq X \leq 600$
  • $1 \leq Y \leq 600$
  • $1 \leq N \leq 100000$
  • $1 \leq x_i \leq 600$
  • $1 \leq y_i \leq 600$
  • $1 \leq v_i \leq 7$
  • All inputs are integers

Sample

Sample 1
Input
4 3
1
1 1 1
Output
5000.000000000000

For example, by moving as shown in the figure below, intersection $(4, 3)$ can be reached in $5000$ seconds.

5
Sample 2
Input
5 4
2
4 1 1
1 2 2
Output
3000.000000000000

For example, by moving as shown in the figure below, intersection $(5, 4)$ can be reached in $3000$ seconds.

4
Sample 3
Input
7 4
3
1 1 1
3 2 2
6 2 3
Output
3800.000000000000
Sample 4
Input
322 274
20
560 364 6
368 247 1
352 15 3
172 43 5
373 478 1
159 334 5
566 206 7
177 393 1
66 273 2
222 154 7
547 166 7
319 321 3
210 426 1
295 514 1
443 472 3
212 403 4
314 244 6
33 63 5
486 326 3
393 203 3
Output
48659.340659340659

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