비행 계획 평가

두 지점 사이를 비행할 때 좋은 비행 계획을 세우는 일은 중요하다. 보통은 연료 소모와 기상 예보, 그중에서도 바람이 문제가 된다. 이 문제에서는 다른 값을 다룬다. 비행 중 얼마나 많은 구간이 바다 위를 지나고 얼마나 많은 구간이 육지 위를 지나는지다. 이 값이 비행 자체를 바꾸지는 않지만, 육지 위를 나는 쪽을 선호하는 승객이 많다. 바다 위를 나는 것이 무섭기도 하고, 육지 위에서는 창밖 풍경이 조금 더 볼 만하기 때문이다.

지구는 반지름이 $6370$ km인 완전한 구라고 가정한다. 각 대륙은 구면 위의 다각형, 즉 선분을 닫힌 순서로 이은 도형으로 나타낸다. 두 점을 잇는 선분은 두 점을 잇는 가장 짧은 대원 호를 뜻한다. 한 선분의 두 끝점이 같은 점이거나 대척점(정반대 지점)인 경우는 없다. 비행 경로도 같은 방식으로 경유점을 선분으로 이은 것이지만, 다각형의 선분과 달리 비행 경로의 선분은 서로 교차해도 되고 출발점으로 돌아오지 않아도 된다.

문제를 간단히 하기 위해 다음 두 가지를 더 가정한다.

• 비행 경로의 어떤 경유점도 해안선, 즉 다각형을 이루는 선분에서 $0.1$ km 이내에 있지 않다.
• 어떤 대륙 다각형의 꼭짓점도 비행 경로에서 $0.1$ km 이내에 있지 않다.

구면 위의 좌표는 위도와 경도의 쌍으로 나타내고 단위는 도이다. 위도가 $\pm 90$인 점은 북극과 남극이고, 위도가 $0$인 점은 적도 위의 점이다.

그림 1. 두 번째 예제 입력

첫째 줄에 대륙의 수를 나타내는 정수 $c$ ($1 \le c \le 30$)가 주어진다.

다음 $c$개의 줄에는 대륙이 한 줄에 하나씩 주어진다. 각 줄은 대륙을 나타내는 다각형의 꼭짓점 개수인 정수 $n$ ($3 \le n \le 30$)으로 시작하고, 이어서 정수 쌍 $\phi_1, \lambda_1, \ldots, \phi_n, \lambda_n$이 주어진다. $\phi_i$와 $\lambda_i$는 $i$번째 꼭짓점의 위도와 경도이며 $-90 \le \phi_i \le 90$, $0 \le \lambda_i \le 359$이다.

마지막 줄에는 비행 계획이 주어진다. 경유점의 개수인 정수 $m$ ($2 \le m \le 30$)으로 시작하고, 이어서 같은 형식으로 정수 쌍 $\phi_1, \lambda_1, \ldots, \phi_m, \lambda_m$이 주어진다.

대륙은 자기 자신과 교차하지 않는다. 어떤 대륙도 다른 대륙과 닿거나 다른 대륙을 포함하지 않는다. 대륙의 꼭짓점은 반시계 방향으로 주어진다. 즉 첫 번째 꼭짓점에서 두 번째 꼭짓점으로 이동하면 대륙의 내부가 왼쪽에 놓인다.

비행 경로의 첫 경유점과 마지막 경유점은 항상 어떤 대륙의 내부에 있다. 두 경유점이 같은 대륙 안에 있을 필요는 없다.

비행 전체 길이 $l$(km)과 비행 중 바다 위를 지나는 비율 $w$(퍼센트)를 한 줄에 공백 하나로 구분해 출력한다. 두 값 모두 소수점 아래 넷째 자리까지 반올림해 정확히 네 자리로 출력한다.