시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 75 31 14 33.333%

문제

강산이는 2012년 런던 올림픽을 본 이후로 취미로 양궁을 하게 되었다.

하지만 생각만큼 양궁은 쉬운 스포츠가 아니었다.

좀처럼 잘 되지 않자 강산이는 좀 더 쉽게 할 수 있는 새로운 양궁을 생각해냈다.

새로운 양궁의 규칙은 다음과 같다.

  • 플레이어는 관통력이 무한하며, 영원히 날아가는 화살을 발사한다.
  • 플레이어의 주변엔 타겟 여러 개가 직선 형태로 놓여 있다. 각 타겟은 교차하거나 겹칠 수도 있다. 단, 플레이어가 타겟 위에 서 있는 경우는 없다.

 

위는 두 개의 타겟이 있는 게임의 예시이다. 플레이어는 원점에서 화살을 쏜다.

각 선수는 어떤 방향으로든 화살을 발사할 수 있다. 예를 들어 위 그림의 경우, 플레이어가 s방향으로 화살을 쏜다면 타겟 T1과 T2 모두를 관통하게 된다. 이 예제에서, 플레이어가 두 개의 타겟을 노릴 수 있는 영역은 한 군데이며, 한 개의 타겟을 노릴 수 있는 영역은 두 군데임을 알 수가 있다. 각 타겟의 끝점을 스치는 화살도 타겟을 관통한 것으로 친다.

강산이는 이 양궁이 아주 마음에 들었다. 특히나, 어떤 선수가 화살을 쏠 때 과연 몇 개의 타겟을 맞힐 수 있을 지를 계산하는 것이 아주 재미있었다.

강산이의 즐거움을 여러분도 체험하기 위해, 각 타겟의 시작점과 끝점이 주어질 때 화살 한 발로 맞힐 수 있는 타겟 수의 기대값을 구해보도록 하자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )

각 테스트 케이스의 첫 줄엔 타겟의 수 N이 주어진다. ( 1 ≤ N ≤ 100 )

이어 N줄에 걸쳐 네 개의 정수 X 1 Y1 X2 Y2가 주어진다. 이는 타겟이 (X1, Y1)에서 시작하여 (X2, Y2)에서 끝나는 선분의 형태로 놓여 있음을 의미한다. ( -100 ≤ X1, Y1, X2,Y2 ≤ 100 )

출력

각 테스트 케이스마다 화살 한 발로 맞힐 수 있는 타겟 수의 기대값을 소수점 여섯 번째 자리에서 반올림하여 다섯 번째 자리까지 출력한다.

예제 입력

2
2
1 5 3 3
3 5 6 2
8
3 0 0 3
0 3 -3 0
-3 0 0 -3
0 -3 3 0
3 3 -3 3
-3 3 -3 -3
-3 -3 3 -3
3 -3 3 3

예제 출력

0.20636
2.00000

힌트