8939번 - Hubble Space Telescope 다국어채점 준비 중

An astrophysicist makes observations of a spiral galaxy known as the Andromeda Galaxy using the Hubble space telescope. In particular, he is interested in the motion of n stars in the galaxy. Each star moves with a constant velocity along a straight line in the picture of the Hubble space telescope. Among the n stars there is a special star named alpha. He wants to know when the maximum distance from alpha to the remaining n-1 stars is minimized.

The picture screen of the Hubble space telescope can be represented by a 2-D Cartesian coordinate system and let S = {s₀,s₁, ..., s_n-1} be a set of n stars in the plane. Assume that the s₀ is the star alpha. A star s_i of S moves along the trajectory p_i + tv_i over time t,where p_i=(x_i,y_i) is the initial position of s_i in the 2-D coordinate system and v_i=(a_i,b_i) is the velocity vector of s_i. We assume that there is no actual collision of two stars, i.e. the two stars pass through each other when they meet a point in 2-D space. Given a set of stars and their velocity, compute the time when the maximum distance from alpha to the remaining stars is minimized within 10⁵ time units. If there is more than one such time, then output the earliest time.

Following figure 1 shows an example with 4 stars. The arrow of a star indicates its velocity vector. In this example, when the time is t=3, the maximum distance from alpha to the remaining 3 stars is minimized. 

(a) at time t=0                                                      (b) at time t=3

Figure 1. An Example. 

Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n (2 ≤ n ≤ 50,000), the number of stars of S. Each of the next n lines contains four integers x_i, y_i and a_i, b_i; (x_i, y_i) is the position of a star s_i at time zero and (a_i, b_i⁾ is the velocity vector of the star s_i (-200,000 ≤ x_i, y_i ≤ 200,000, -500 ≤ a_i, b_i ≤ 500). Two or more stars of S may have the same coordinates at time zero. 

Your program is to write to standard output. Print the time when the maximum distance is minimized from s₀ (alpha) to the remaining n-1 stars {s_o, s₁, ... , s_n-1} within 10⁵ time units, rounded to 4 fractional digits.

The following shows sample input and output for five test cases.