데카르트 작업

킬로그램의 표준 역할을 하는 백금-이리듐 원기둥에 대해서는 들어 보았을 수도 있지만, 킬로미터의 표준으로 사용되는 특별한 선분이 있다는 사실을 알고 있었는가? 이 선분은 기밀이 유지되는 매우 평평한 장소의 2D 평면에서 (0, 0)부터 (0, 1000)까지 이어진다.

당연히 이 선분은 매우 귀중하므로, 2D 평면상의 반직선인 N개의 회전식 감시 레이저가 이를 보호한다. 각 레이저에는 고정된 끝점이 있으며, 그 끝점을 중심으로 초당 1회전의 일정한 속도로 회전한다. 각 레이저가 시계 방향으로 회전할지 반시계 방향으로 회전할지는 보안 시스템이 균등하고 독립적으로 무작위 선택한다.

레이저는 다른 레이저나 그 끝점 또는 선분 자체에 의해 차단되지 않는다. 어떤 레이저도 선분 위에 끝점을 두지 않는다.

당신은 보안 시스템을 감사하도록 고용되었지만, 활용할 수 있는 것은 한순간을 포착하여 각 레이저의 끝점과 그 순간의 방향을 보여 주는 단 하나의 스냅사진뿐이다. 이 이미지는 단지 스냅사진이므로 레이저의 회전 방향을 추론할 방법은 없다.

어떤 레이저도 선분에 닿지 않는 비어 있지 않은 열린 시간 구간이 단 한 번이라도 존재한다면, 강도 사건으로 선분을 훔칠 수 있다고 판단했다. 이런 일이 일어날 확률은 얼마인가?

제한

1 ≤ T ≤ 100. 테스트 세트별 시간 제한: 40초. 메모리 제한: 1GB. -$10^{6}$ ≤ $X_{i}$ ≤ $10^{6}$, 모든 i에 대해. -$10^{6}$ ≤ $Y_{i}$ ≤ $10^{6}$, 모든 i에 대해. -$10^{6}$ ≤ $X_{i}$' ≤ $10^{6}$, 모든 i에 대해. -$10^{6}$ ≤ $Y_{i}$' ≤ $10^{6}$, 모든 i에 대해. ($X_{i}$, $Y_{i}$) ≠ ($X_{i}$', $Y_{i}$'), 모든 i에 대해. 모든 i에 대해, $X_{i}$ = 0이면 $Y_{i}$ < 0이거나 $Y_{i}$ > 1000이다. (어떤 레이저의 끝점도 선분 위에 있지 않다.)

테스트 세트 1 (공개)

1 ≤ N ≤ 10.

테스트 세트 2 (비공개)

1 ≤ N ≤ 10000. N > 100인 케이스는 최대 8개이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 케이스는 레이저의 수를 나타내는 정수 N 하나가 포함된 한 줄로 시작한다. 이어서 N개의 줄이 더 주어진다. 이 중 i번째 줄은 i번째 레이저인 반직선을 나타내며, 네 정수 $X_{i}$, $Y_{i}$, $X_{i}$', $Y_{i}$'가 주어진다. 이들은 반직선 끝점의 2D 좌표와 그 뒤를 잇는 반직선 위 다른 한 점의 2D 좌표를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 위에서 설명한 확률이다. y이 정답과의 절대 오차 또는 상대 오차가 10^{-6} 이내이면 정답으로 간주한다. 이것이 무엇을 의미하는지와 허용되는 실수 형식에 관한 설명은 FAQ을 참조하라.

예제 케이스 #1에서 여러 레이저가 같은 끝점과 초기 방향을 공유할 수도 있지만, 그렇다고 해서 반드시 같은 방향으로 회전하는 것은 아니다. (또한 두 번째 레이저와 세 번째 레이저는 서로 다르게 지정되어 있지만 초기 방향이 같다는 점에도 유의하라.) 하지만 회전 방향과 관계없이 각 레이저는 음의 y 방향을 가리키는 순간에만 선분에 닿으므로, 어떤 레이저도 선분에 닿지 않는 다른 열린 시간 구간이 분명히 존재하며 답은 1이다.

예제 케이스 #2에서 각 레이저는 회전 주기의 정확히 1/4 동안 선분에 닿는다. 레이저 1과 4이 같은 방향으로 회전하고 레이저 2과 3이 같은 방향으로 회전할 때, 그리고 그럴 때에만 선분은 항상 레이저에 닿는다. 그 확률은 1/4이므로 답은 3/4이다.

예제 케이스 #3은 예제 케이스 #2과 비슷하지만, 레이저가 모두 같은 방향으로 회전하더라도 어떤 레이저도 선분에 닿지 않는 순간이 존재함을 보장하는 약간의 차이가 있다. 따라서 답은 1이다.