시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

2 초 | 256 MB | 176 | 26 | 21 | 15.328% |

A histogram is a simple rectilinear polygon whose boundary consists of two chains such that the upper chain is monotone with respect to the horizontal axis and the lower chain is a horizontal line segment, called the base segment (See Figure 1).

Figure 1. A histogram and its base segment (v_{0}, v_{1})

Let P be a histogram specified by a list (v_{0}, v_{1}, … ,v_{n-1}) of n vertices in the counterclockwise order along the boundary such that its base segment is (v_{0}, v_{1}). An edge e_{i} is a line segment connecting two vertices v_{i} and v_{i+1}, where i = 0, 1, … , n − 1 and v_{n} = v_{0}.

A path inside P is a simple path which does not intersect the exterior of P. The length of the path is defined as the sum of Euclidean length of the line segments of the path. The distance between two points p and q of P is the length of the shortest path inside P between p and q. Your task is to find the distance between v_{0} and each point of a given set S of points on the boundary of P. A point of the set S is denoted by p(k, d) which represents a point q on the edge e_{k} such that d is the distance between v_{k} and q.

In the histogram of Figure 1, the shortest path between v_{0} and q_{1} = p(10, 2) is a polygonal chain connecting 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 a segment directly connecting v_{0} and q_{2} with length 15.033296.

Given a histogram P with n vertices and a set S of m points on the boundary of P, write a program to find the distances between v_{0} and all points of S.

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer, n (4 ≤ n ≤ 100,000), where n is the number of vertices of a histogram P = (v_{0}, v_{1}, … , v_{n-1}). In the following n lines, each of the n vertices of P is given line by line from v_{0} to v_{n-1}. Each vertex is represented by two numbers, which are the x-coordinate and the y-coordinate of the vertex, respectively. Each coordinate is given as an integer between 0 and 1,000,000, inclusively. Notice that (v_{0}, v_{1}) is the base segment. The next line contains an integer m (1 ≤ m ≤ 100,000) which is the size of a set S given as your task. In the following m lines. Each point p(k,d) of S is given line by line, and is represented by two integers k and d, where 0 ≤ k ≤ n − 1 and 0 ≤ d < the length of edge e_{k}. All points in the set S are distinct.

Your program is to write to standard output. Print exactly one line for each test case. The line should contain exactly one real value which is the sum of the distances between v_{0} and all points of S. Your output must contain the first digit after the decimal point, rounded off from the second digit. If each result is within an error range, 0.1, it will be considered correct. 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}\)

2 16 0 0 15 0 15 4 13 4 13 6 10 6 10 2 7 2 7 5 6 5 6 7 3 7 3 3 2 3 2 1 0 1 2 10 2 1 1 8 100000 100000 400000 100000 400000 200000 300000 200000 300000 300000 200000 300000 200000 200000 100000 200000 8 1 0 2 0 3 0 4 0 5 0 6 0 7 0 1 50000

23.6 1909658.1