아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

양궁

시간 제한1초메모리 제한128 MB

요약
원점에서 균일한 무작위 방향으로 쏜 광선이 주어진 선분 중 몇 개를 뚫는지 기댓값을 구합니다.
난이도

보통10점 중 5점

유형
기하, 확률
정답자
아직 제출이 없습니다

문제

강산이는 2012년 런던 올림픽을 보고 취미로 양궁을 시작했다. 그런데 양궁은 생각만큼 쉬운 운동이 아니었다. 실력이 좀처럼 늘지 않아서 강산이는 훨씬 쉬운 새 양궁 규칙을 만들었다.

  • 플레이어는 원점에 서서 화살 한 발을 쏜다. 화살은 관통력이 무한하고, 쏜 방향으로 영원히 날아간다.
  • 화살을 쏘는 방향은 모든 방향에 대해 균등하게 정해진다. 즉 화살의 각도는 [0,2π)[0, 2\pi) 구간의 균등분포를 따른다.
  • 타겟은 평면 위의 선분이고 여러 개가 놓여 있다. 타겟끼리 서로 교차하거나 겹칠 수도 있다. 원점을 지나는 타겟은 없으므로 플레이어가 타겟 위에 서 있는 경우도 없다.
  • 원점에서 뻗어 나가는 반직선과 만나는 타겟은 화살이 모두 관통한다. 타겟의 끝점을 스치기만 한 화살도 관통한 것으로 센다.

타겟이 두 개인 경우를 생각해 보자. 한 발로 두 타겟을 모두 관통하는 방향이 있고, 한 타겟만 관통하는 방향이나 아무것도 맞히지 못하는 방향도 있다. 강산이는 활을 직접 쏘는 것보다 화살 한 발로 타겟을 몇 개 맞히게 될지 계산하는 쪽이 더 재미있었다.

각 타겟의 두 끝점이 주어질 때, 화살 한 발로 관통하는 타겟 수의 기댓값을 구하자.

입력

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

각 테스트 케이스의 첫 줄에 타겟의 수 NN 이 주어진다. (1≤N≤1001 \le N \le 100)

이어지는 NN 줄에 정수 X1X_1, Y1Y_1, X2X_2, Y2Y_2 가 공백으로 구분되어 주어진다. 이 타겟은 (X1,Y1)(X_1, Y_1) 에서 (X2,Y2)(X_2, Y_2) 까지 이어지는 선분이다. (−100≤X1,Y1,X2,Y2≤100-100 \le X_1, Y_1, X_2, Y_2 \le 100)

출력

각 테스트 케이스마다 화살 한 발로 관통하는 타겟 수의 기댓값을 한 줄에 출력한다. 소수점 여섯째 자리에서 반올림해 다섯째 자리까지 적는다. 채점 데이터에서는 반올림 결과가 애매해지는 값이 나오지 않는다.

예제1

  1. 예제 1

    입력
    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