Path Inside a Histogram

A histogram is a simple rectilinear polygon whose boundary consists of two chains. The upper chain is monotone with respect to the horizontal axis, and the lower chain is a single horizontal segment called the base segment.

Figure 1. A histogram and its base segment $(v_0, v_1)$

Let $P$ be a histogram given by the list $(v_0, v_1, \dots, v_{n-1})$ of its $n$ vertices in counterclockwise order along the boundary, where the base segment is $(v_0, v_1)$. The edge $e_i$ is the segment joining the vertices $v_i$ and $v_{i+1}$, for $i = 0, 1, \dots, n-1$ with $v_n = v_0$.

A path inside $P$ is a simple path that does not intersect the exterior of $P$. The length of a path is the sum of the Euclidean lengths of its segments. The distance between two points $p$ and $q$ of $P$ is the length of the shortest path inside $P$ between them. A point on the boundary written $p(k, d)$ is the point on the edge $e_k$ whose distance from $v_k$ is $d$.

In the histogram of Figure 1, the shortest path between $v_0$ and $q_1 = p(10, 2)$ is the polygonal chain through $v_0$, $v_{14}$, $v_{12}$ and $q_1$ in that order, and its length is $8.595242$. The shortest path between $v_0$ and $q_2 = p(1, 1)$ is the segment joining the two points directly, and its length is $15.033296$.

You are given a histogram $P$ with $n$ vertices and a set $S$ of $m$ points on the boundary of $P$. Write a program that finds the distances between $v_0$ and all points of $S$.

Your program reads from standard input. The first line contains the number of test cases $T$.

The first line of each test case contains the number of vertices $n$ of the histogram $P = (v_0, v_1, \dots, v_{n-1})$. ($4 \le n \le 100\,000$)

Each of the next $n$ lines contains one vertex, from $v_0$ to $v_{n-1}$, given as two integers, the x-coordinate and the y-coordinate of that vertex. Both coordinates are between $0$ and $1\,000\,000$, inclusive. The segment $(v_0, v_1)$ is the base segment.

The next line contains the size $m$ of the set $S$. ($1 \le m \le 100\,000$)

Each of the next $m$ lines contains one point $p(k, d)$ of $S$ as two integers $k$ and $d$. ($0 \le k \le n-1$, $0 \le d <$ the length of the edge $e_k$) All points of $S$ are distinct.

Your program writes to standard output. For each test case, print on one line the sum of the distances between $v_0$ and all points of $S$. Round the sum at the second digit after the decimal point and print exactly one digit after the decimal point.

The Euclidean distance between two points $p = (x_1, y_1)$ and $q = (x_2, y_2)$ is $\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$.