4715번 - Two Mountaineers 다국어

Two mountain climbers are located at opposite ends of a mountain range, at the same elevation. The two climbers want to walk along the mountain range and reach each other’s starting place, while always staying at the same elevation. The climbers may move forward or backward to assure that they stay at the same elevation. It is well known that it is always possible for the two climbers to reach each other’s starting place if the mountain range never drops below the starting elevation. Given a mountain range, compute the minimum sum of the two walk lengths of the two climbers to reach each other’s starting place from their own starting place.

Mountain range is represented as a polygonal line P = (p₁, p₂, …, p_n) in the plane with point set{p_i = (x_i, y_i) : i = 1,…,n} and edge set {(p_i, p_i+1) : i=1, …, n-1}. The polygonal line P modeling a mountain range is monotone with respect to the x-coordinate axis, i.e.x_i < x_i+1 for i = 1,
, n −1(see the following figure).

A walk of a climber along a mountain range P is a sequence W = (w₁, w₂, …, w_m) of points w_j ∈ P such that every line-segment of a walk must be on P , i.e., (w_j,w_j+1) ⊂ P for j = 1,
,m −1. We compute the length of a walk along a line-segment (w_j,w_j+1) of W as the difference of the y-coordinates of w_j and w_j+1, i.e., the distance is |y_i - y_i-1| where y_i(y_i+1) is the y-coordinate of w_i(w_i+1), respectively. The length of a walk W is the sum of the lengths of the line-segments of W.

For example, in the above figure, the walk of the left climber is (a, d, c, e, g, f, h, j, i, l, o, p, r, p, o, m, o, p, s), and the sum of walk lengths for the two climbers is 120. We can see that the length is the shortest length of walks by the climbers.

The input consists of T test cases. The number of test cases T (1 ≤ T ≤ 3) is given in the first line of the input file. The first line of each test case contains an integer n (3 ≤ n ≤ 1000), which is the number of points in a polygonal line P representing a mountain range. In the following n lines, coordinates of points in P come in the order of p₁, p₂, …, p_n. Each line contains two integers n_x and n_y (0 ≤ n_x, n_y ≤ 10000), where n_x is the x-coordinate and n_y is the y-coordinate of a point of P. One mountain climber starts at p₁, and the other starts at p_n. Therefore, the y-coordinates of p₁ and p_n must be the same. You may assume that for each input test case, the mountain range never drops below the starting elevation and the y-coordinate of p_i,1≤ i ≤ n, is unique.

For each test case, your program reports, on each line, the minimum length of walks by the two climbers.

The following sample input and corresponding correct output represents three test cases.