Given n segments in the two dimensional space. The i-th segment connects the points. ). Apollo wants to select n points from the given n segments. The i-th point. ) should lie in the i-th segment. That is say, the i-th points. The Euclidean distance between the two points with numbers i and j is said to be:. . We say that the length of the path formed by the n points is value. Apollo gives you the starting and ending points of n segments. You have to find n points for him, to minumize the length of the path formed by the n points.
Apollo isn't well prepared on geometry problems, but he heard that this year there will be a lot of geometry problems on the ICPC. Scared, Apollo locked himself in the basement and started thinking of new problems of this kind. One of them is the following. Given n segments (numbered from 1 to n) in the two dimensional space. The i-th segment connects the points (i, l_i) (i,l i ) and (i, r_i) (i,r i ). Apollo wants to select n points from the given n segments. The i-th point (x_i, y_i) (x i ,y i ) should lie in the i-th segment. That is say, the i-th points (x_i, y_i) (x i ,y i ) should meet x_i = i x i =i and l_i le y_i le r_i l i ≤y i ≤r i . The Euclidean distance between the two points with numbers i and j is said to be: dist(i, j) = sqrt{(x_i - x_j)^2 + (y_i - y_j)^2} dist(i,j)= (x i −x j ) 2 +(y i −y j ) 2 . We say that the length of the path formed by the n points is value sum_{i=1}^{n-1}dist(i, i+1) ∑ i=1 n−1 dist(i,i+1). Apollo gives you the starting and ending points of n segments. You have to find n points for him, to minumize the length of the path formed by the n points.
