히스토그램 안의 최단 경로

히스토그램은 경계가 두 사슬로 이루어진 단순 직교 다각형이다. 위쪽 사슬은 가로축에 대해 단조이고, 아래쪽 사슬은 수평 선분 하나이다. 이 수평 선분을 밑변이라고 한다.

그림 1. 히스토그램과 밑변 $(v_0, v_1)$

히스토그램 $P$의 꼭짓점 $n$개를 경계를 따라 반시계 방향으로 나열한 것을 $(v_0, v_1, \dots, v_{n-1})$이라고 하자. 밑변은 $(v_0, v_1)$이다. 변 $e_i$는 꼭짓점 $v_i$와 $v_{i+1}$을 잇는 선분이고, $i = 0, 1, \dots, n-1$이며 $v_n = v_0$이다.

$P$ 안의 경로는 $P$의 외부와 만나지 않는 단순 경로이다. 경로의 길이는 경로를 이루는 선분의 유클리드 길이를 모두 더한 값이다. $P$ 위의 두 점 $p$와 $q$ 사이의 거리는 $P$ 안에서 두 점을 잇는 최단 경로의 길이이다. 경계 위의 점 $p(k, d)$는 변 $e_k$ 위에 있으면서 $v_k$에서의 거리가 $d$인 점을 뜻한다.

그림 1의 히스토그램에서 $v_0$과 $q_1 = p(10, 2)$ 사이의 최단 경로는 $v_0$, $v_{14}$, $v_{12}$, $q_1$을 차례로 잇는 꺾은선이고, 길이는 $8.595242$이다. $v_0$과 $q_2 = p(1, 1)$ 사이의 최단 경로는 두 점을 곧바로 잇는 선분이고, 길이는 $15.033296$이다.

꼭짓점이 $n$개인 히스토그램 $P$와 그 경계 위의 점 $m$개로 이루어진 집합 $S$가 주어진다. $v_0$과 $S$의 모든 점 사이의 거리를 구하는 프로그램을 작성하시오.

입력은 표준 입력으로 주어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 히스토그램 $P = (v_0, v_1, \dots, v_{n-1})$의 꼭짓점 개수 $n$이 주어진다. ($4 \le n \le 100\,000$)

다음 $n$개의 줄에 $v_0$부터 $v_{n-1}$까지 꼭짓점이 한 줄에 하나씩 주어진다. 각 줄에는 그 꼭짓점의 x좌표와 y좌표를 나타내는 정수 두 개가 주어지고, 두 좌표 모두 $0$ 이상 $1\,000\,000$ 이하이다. $(v_0, v_1)$이 밑변이다.

다음 줄에 집합 $S$의 크기 $m$이 주어진다. ($1 \le m \le 100\,000$)

다음 $m$개의 줄에 $S$의 점 $p(k, d)$가 한 줄에 하나씩 정수 두 개 $k$와 $d$로 주어진다. ($0 \le k \le n-1$, $0 \le d <$ 변 $e_k$의 길이) $S$의 점은 모두 서로 다르다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 한 줄에 $v_0$과 $S$의 모든 점 사이의 거리를 더한 값을 출력한다. 소수점 아래 둘째 자리에서 반올림해 소수점 아래 첫째 자리까지 정확히 출력한다.

두 점 $p = (x_1, y_1)$과 $q = (x_2, y_2)$ 사이의 유클리드 거리는 $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$이다.