시간 제한메모리 제한제출정답맞힌 사람정답 비율
40 초 (추가 시간 없음) 1024 MB0000.000%

문제

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 Xi, Yi, Xi', and Yi', 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.
  • -106Xi ≤ 106, for all i.
  • -106Yi ≤ 106, for all i.
  • -106Xi' ≤ 106, for all i.
  • -106Yi' ≤ 106, for all i.
  • (Xi, Yi) ≠ (Xi', Yi'), for all i.
  • If Xi = 0, then either Yi < 0 or Yi > 1000, for all i. (No laser's endpoint is on the segment.)

Test Set 1 (10점)

  • 1 ≤ N ≤ 10.

Test Set 2 (38점)

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

예제 입력 1

3
5
0 1001 -1 1001
0 1001 -1 1001
0 1001 -2 1001
0 1001 0 500
0 1002 1234 5678
4
500 500 1000 1000
500 500 0 1000
500 500 0 0
500 500 1000 0
4
500 500 1000 1001
500 500 0 1000
500 500 0 0
500 500 1000 0

예제 출력 1

Case #1: 1.000000
Case #2: 0.750000
Case #3: 1.000000

힌트

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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.