카테시안 작업

킬로그램의 표준으로 쓰이는 백금-이리듐 원기는 들어봤을 것이다. 그런데 킬로미터의 표준으로 쓰이는 특별한 선분이 있다는 것은 알고 있는가? 이 선분은 2차원 평면의 (0, 0)에서 (0, 1000)까지 이어져 있으며, 비밀스럽고 아주 평평한 장소에 놓여 있다.

이 선분은 매우 가치가 높아서 N개의 회전하는 감시 레이저가 지킨다. 레이저는 2차원 평면의 반직선이다. 각 레이저는 고정된 끝점을 가지며, 그 끝점을 중심으로 초당 1회전의 일정한 속력으로 회전한다. 각 레이저가 시계 방향으로 돌지 반시계 방향으로 돌지는 보안 시스템이 균등하고 독립적으로 무작위로 정한다.

레이저는 다른 레이저나 그 끝점, 또는 선분 자체에 의해 막히지 않는다. 어떤 레이저의 끝점도 선분 위에 있지 않다.

당신은 이 보안 시스템을 감사하는 일을 맡았지만, 주어진 것은 한 순간을 찍은 스냅샷뿐이다. 스냅샷에는 각 레이저의 끝점과 그 순간의 방향이 나타나 있다. 스냅샷이므로 레이저의 회전 방향은 추론할 수 없다.

선분에 어떤 레이저도 닿지 않는 시간 구간이 공집합이 아닌 열린 구간으로 존재하면, 선분은 도둑맞을 수 있다. 이런 일이 일어날 확률은 얼마인가?

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 레이저의 개수 $N$이 적힌 한 줄로 시작한다. 이어서 $N$개의 줄이 주어지며, $i$번째 줄은 $i$번째 레이저를 나타낸다. 이 줄에는 정수 $X_i$, $Y_i$, $X_i'$, $Y_i'$가 주어진다. 앞의 두 값은 끝점의 2차원 좌표이고, 뒤의 두 값은 그 반직선 위에 있는 다른 한 점의 2차원 좌표이다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 위에서 설명한 확률이다. 절대 오차 또는 상대 오차가 정답의 $10^{-6}$ 이내이면 정답으로 인정한다.

• $1 \le T \le 100$
• 모든 $i$에 대해 $-10^6 \le X_i \le 10^6$
• 모든 $i$에 대해 $-10^6 \le Y_i \le 10^6$
• 모든 $i$에 대해 $-10^6 \le X_i' \le 10^6$
• 모든 $i$에 대해 $-10^6 \le Y_i' \le 10^6$
• 모든 $i$에 대해 $(X_i, Y_i) \ne (X_i', Y_i')$
• $X_i = 0$이면 모든 $i$에 대해 $Y_i < 0$ 또는 $Y_i > 1000$이다. (어떤 레이저의 끝점도 선분 위에 있지 않다.)

샘플 케이스 #1에서는 여러 레이저가 같은 끝점과 같은 초기 방향을 가지지만, 그렇다고 같은 방향으로 회전한다는 뜻은 아니다. (두 번째와 세 번째 레이저도 초기 방향은 같지만 표현 방식이 다르다.) 회전 방향과 상관없이 이 레이저들은 각각 음의 y 방향을 가리키는 순간에만 선분에 닿는다. 따라서 어떤 레이저도 선분에 닿지 않는 다른 열린 구간이 분명히 존재하며, 답은 1이다.

샘플 케이스 #2에서는 각 레이저가 회전의 정확히 1/4 동안만 선분에 닿는다. 레이저 1과 4가 같은 방향으로 회전하고 레이저 2와 3도 같은 방향으로 회전할 때에만 어느 순간에나 선분에 레이저가 닿는다. 그 확률은 1/4이므로 답은 3/4이다.

샘플 케이스 #3은 샘플 케이스 #2와 비슷하지만, 모든 레이저가 같은 방향으로 회전하더라도 어떤 레이저도 선분에 닿지 않는 순간이 반드시 생기도록 조금 다르게 설정되어 있다. 따라서 답은 1이다.