← 返回题目列表

AtCoder · test001_f

F. THE☆章鱼烧节2012

中文机器翻译题面 查看原题

問題文

在章鱼烧店开业时,为了让大家了解章鱼烧的味道,决定举行试吃活动。
但是,高桥社长希望更多的人品尝章鱼烧,所以提出了兼作试吃活动的祭典“THE☆章鱼烧祭2012”。高桥社长提出的‘THE☆章鱼烧祭2012’的试吃活动内容如下。

会场中共有你和参加者人数的总和 N 人。你手里有 N 个章鱼烧,并将它们分给每位参与者,每人分到 1 人 1 个。
会场很大,所以你必须扔着章鱼烧来分发。 仅靠你一个人分发给所有人很困难,所以也让参与者协助,参与者也可以把收到的章鱼烧投给其他参与者。
你和参与者有牙签1 每人 1 由于我只有书,所以我不能同时扔多个章鱼烧,并且在扔完章鱼烧后, 在 1 秒内你不能再扔一个章鱼烧。收件人可以随时收到任意数量的物品。
此外,您和您的参与者不得离开站立位置。
参与者范围从成人到儿童,因此每个人接住章鱼烧的速度都有上限,投掷章鱼烧的人也有投掷章鱼烧的速度上限。投掷的章鱼烧到达接收者的速度没有衰减。

既然我们想让大家吃到新鲜出炉的章鱼烧,请回答将章鱼烧分发给大家所需的最短时间。


入力

输入是按以下格式从标准输入给出的。
N
x_{0} y_{0} t_{0} r_{0}
x_{1} y_{1} t_{1} r_{1}
:
:
x_{N-1} y_{N-1} t_{N-1} r_{N-1}
  • 输入是 有一条 N+1 行。
  • 1 行是一个整数,表示章鱼烧节的参加人数加上您。 N\ (1≦N≦1,000) 。
  • 2 线显示您所在的位置。 x 代表坐标的整数 x_0\ (-10,000≦x_0≦10,000)、y 代表坐标的整数 y_0\ (-10,000≦y_0≦10,000),一个整数,代表投掷章鱼烧的速度上限 t_0\ (3≦t_0≦340) 表示章鱼烧接收速度上限的整数。 第 r_0\ (3≦r_0≦340) 用空格分隔。
  • 3 从行 N-1 行数过多 i+2\ (1≦i≦N-1) 在线 写在方格 i 位参与者站立的位置。 x 代表坐标的整数 x_i\ (-10,000≦x_i≦10,000)、y 代表坐标的整数 y_i\ (-10,000≦y_i≦10,000),一个整数,代表投掷章鱼烧的速度上限 t_i\ (3≦t_i≦340) 表示章鱼烧接收速度上限的整数。 第 r_i\ (3≦r_i≦340) 用空格分隔。
  • 给定速度为 1 速度约为秒。
  • 多个人永远不会站在同一个位置。

出力

章鱼烧适用于所有参与者 1 接收每个请求所需的最短秒数 1 行。
输出仅为整数和小数,误差至少为绝对误差或相对误差之一。 10^{−6} 如果低于则允许。
请在末尾输出换行符。

入力例 1

4
0 0 300 10
0 100 10 100
0 200 10 200
0 300 10 300

出力例 1

3
  • 0 秒目 :
    • 你: 速度到达第 1 位参与者 100 扔章鱼烧。
  • 1 秒目 :
    • 你: 速度到达第 2 位参与者 200 扔章鱼烧。
    • 1 第参与者:你 0 第二个接住抛出的章鱼烧。
  • 2 秒目 :
    • 你: 速度到达第 3 位参与者 300 扔章鱼烧。
    • 2 第参与者:你 1 第二个接住抛出的章鱼烧。
  • 3 秒目 :
    • 3 第参与者:你 2 第二个接住抛出的章鱼烧。

入力例 2

4
0 0 100 10
0 90 10 10
0 100 30 100
-20 100 10 10

出力例 2

3
  • 0 秒目 :
    • 你: 速度到达第 2 位参与者 100 扔章鱼烧。
  • 1 秒目 :
    • 你: 速度到达第 2 位参与者 100 扔章鱼烧。
    • 2 第参与者:你 0 接住第二个扔出的章鱼烧, 用3 位参与者 10 抛出。
  • 2 秒目 :
    • 你: 速度到达第 2 位参与者 100 扔章鱼烧。
    • 2 第参与者:你 1 接住第二个扔出的章鱼烧, 用2 位参与者 10 抛出。
  • 3 秒目 :
    • 1 第参与者: 2 第参与者 2 第二个接住抛出的章鱼烧。
    • 2 第参与者:你 2 第二个接住抛出的章鱼烧。
    • 3 第参与者: 2 第参与者 1 第二个接住抛出的章鱼烧。

入力例 3

1
0 0 3 3

出力例 3

0
  • 由于您是唯一的参与者,因此无需分发它们。

入力例 4

4
58 -49 38 109
45 -29 200 56
-32 123 103 98
49 -234 289 43

出力例 4

4.874179

入力例 5

8
100 100 30 50
100 50 93 123
100 0 89 111
50 100 13 18
50 0 155 86
0 100 30 58
0 50 58 49
0 0 98 153

出力例 5

7.666667