33OJ
登录 注册

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

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

[JAG 2026 Summer Camp #3] Line Up!

Problem Description

There are NN people on a two-dimensional plane. The ii-th person is initially located at (xi,yi)(x_i,y_i) and can move freely in any direction at a speed of at most viv_i units per second.

They all want to line up on a single straight line. Find the minimum time required for them to do so.

More precisely, find the minimum nonnegative real number TT for which there exists a straight line such that every person can reach some point on it within TT seconds.

The position and orientation of the line may be chosen freely. Multiple people may occupy the same point.

Input Format

The input consists of a single test case of the following format.

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

The first line contains an integer NN (3≤N≤10003\le N\le1000), representing the number of people.

For each ii (1≤i≤N1\le i\le N), the ii-th of the following NN lines contains three integers xix_i, yiy_i, and viv_i (−109≤xi,yi≤109-10^9\le x_i,y_i\le10^9, 1≤vi≤1051\le v_i\le10^5). The ii-th person is initially located at (xi,yi)(x_i,y_i) and has a maximum speed of viv_i units per second.

Output Format

Print a single real number representing the minimum time required for all NN people to be located on a single straight line.

Your answer will be considered correct if its absolute or relative error does not exceed 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