33OJ
登录 注册

#P17574. [JAG 2026 Summer Camp #3] Line Up!

    ID: 20282 远端评测题 2000ms 2048MiB 尝试: 0 已通过: 0 显示难度提高+/省选− 上传者: 标签>数学Special JudgeICPC2026单调栈

[JAG 2026 Summer Camp #3] Line Up!

题目描述

二维平面上有 NN 个人。第 ii 个人最初位于 (xi,yi)(x_i,y_i),可以以每秒至多 viv_i 个单位长度的速度自由地向任意方向移动。

他们想要全部排在同一条直线上。求实现这一目标所需的最短时间。

更准确地说,求最小的非负实数 TT,使得存在一条直线,每个人都能在 TT 秒内到达该直线上的某个点。

可以自由选择这条直线的位置和方向。多个人可以位于同一个点。

输入格式

输入包含一组测试数据,格式如下。

N
x_1 y_1 v_1
x_2 y_2 v_2
...
x_N y_N v_N

第一行包含一个整数 NN(3≤N≤10003\le N\le1000),表示人数。

对于每个 ii(1≤i≤N1\le i\le N),接下来 NN 行中的第 ii 行包含三个整数 xi,yi,vix_i,y_i,v_i(−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9,1≤vi≤1051\le v_i\le10^5)。第 ii 个人最初位于 (xi,yi)(x_i,y_i),最大移动速度为每秒 viv_i 个单位长度。

输出格式

输出一个实数,表示使全部 NN 个人位于同一条直线上所需的最短时间。

如果答案的绝对误差或相对误差不超过 10−710^{-7},则会被判为正确。

3
0 0 2
2 0 1
0 -2 1
0.471404520791
4
0 0 1
0 0 2
0 0 3
0 0 4
0.000000000000
26
226639011 714030491 52084
-433602126 -108920882 63933
529792924 -599056247 51073
447686200 -908930834 96957
752558066 -98596171 12331
-325499883 966751315 64309
507655993 356046254 24621
323698442 815958050 1579
-797812857 -247507527 45097
952346469 565751814 86072
-631841229 823378480 3226
-139573806 864389108 31195
-238947644 27719504 22660
-834033851 -831292724 26624
947551802 -473531913 65103
829291610 99663009 45079
-764217971 -751329486 28073
-687089797 -200100828 3458
-597429979 -713064249 94885
273582861 727423928 31031
-423665895 -244614618 46129
310263329 834575868 19397
556376001 -539503889 51869
452257555 672020980 48905
-244101763 708382053 51097
-724609724 489151554 38920
118687.975695169065