27769번 - The Cartesian Job 서브태스크스페셜 저지다국어

You may have heard of the platinum-iridium cylinder that serves as the standard for the kilogram, but did you know that there is a special line segment used as the standard for the kilometer? It runs from (0, 0) to (0, 1000) in a 2D plane in a confidential and very flat location.

Naturally, this segment is extremely valuable, so it is protected by N rotating surveillance lasers, which are rays in the 2D plane. Each laser has a fixed endpoint, and it rotates around that endpoint at a constant speed of 1 revolution per second. Whether each laser rotates clockwise or counterclockwise is chosen uniformly and independently at random by the security system.

Lasers are not blocked by other lasers or their endpoints, or the segment itself. No laser has an endpoint on the segment.

You have been hired to audit the security system, but all you have to work with is a single snapshot from an instant in time, which shows the endpoint and orientation (at that instant) of each laser. Since the image is just a snapshot, you have no way of inferring the rotation directions of the lasers.

You have determined that the segment could be stolen in a heist if there is ever a non-empty open interval of time during which no laser is touching the segment. What is the probability of this happening?

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing one integer N: the number of lasers. Then, N more lines follow. The i-th of these lines represents the ray that is the i-th laser, and contains four integers X_i, Y_i, X_i', and Y_i', representing the 2D coordinates of the endpoint of the ray, followed by the 2D coordinates of some other point on the ray.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the probability described above. y will be considered correct if it is within an absolute or relative error of 10^-6 of the correct answer.

• 1 ≤ T ≤ 100.
• -10⁶ ≤ X_i ≤ 10⁶, for all i.
• -10⁶ ≤ Y_i ≤ 10⁶, for all i.
• -10⁶ ≤ X_i' ≤ 10⁶, for all i.
• -10⁶ ≤ Y_i' ≤ 10⁶, for all i.
• (X_i, Y_i) ≠ (X_i', Y_i'), for all i.
• If X_i = 0, then either Y_i < 0 or Y_i > 1000, for all i. (No laser's endpoint is on the segment.)

• 1 ≤ N ≤ 10.

• 1 ≤ N ≤ 10000.
• There are at most 8 cases with N > 100.

In Sample Case #1, note that multiple lasers might share the same endpoint and initial orientation, but this does not necessarily imply that they rotate in the same direction. (Also note that the second and third lasers have the same initial orientation even though it is specified differently.) Regardless of their rotation directions, though, each of these lasers only touches the segment at the instant that it is pointing in the negative y direction, so there is clearly some other open interval during which no laser is touching the segment, and the answer is 1.

In Sample Case #2, each of the lasers touches the segment during exactly 1/4 of its rotation, and the segment will be touched by a laser at all times if and only if lasers 1 and 4 rotate in the same direction, and lasers 2 and 3 rotate in the same direction. The probability of that is 1/4, so the answer is 3/4.

Sample Case #3 is like Sample Case #2, but with a slight difference that guarantees that there will be an instant at which no laser is touching the segment, even if the lasers are all rotating the same way. So the answer is 1.