{"raw_statement":[{"iden":"statement","content":"Another asteroid hit Mars. Fortunately, no Martians were hurt this time. Scotty, the king of Mars, decided to build force fields to protect the human colonies on Mars. As (not many) people know, building force fields costs a lot of energy, therefore he wants to minimize the total length of the force fields, can you help him? \n\nYou can imagine Mars as a 2D plane (y = 0 represents the surface of the planet) where each colony is a point with integer coordinates (xi, yi) (yes, there are flying colonies in Mars). A force field is a polyline that starts in one of the colonies and ends in another. You can build as many force fields as you want, as long as the following rules are satisfied: \n\n \n\n A colony with coordinates (x, y) is covered by a force field that starts in x1 and ends in x2 along the X axis, if x1 ≤ x ≤ x2 and y ≤ f(x) where f(x) is the y coordinate of the point of the force field polyline with X coordinate x. What is the minimum total length of force fields that is needed to cover all colonies? \n\n \n\nThe first line contains one integer T, the number of test cases. Each test case consists of two lines, the first one contains an integer n, the number of colonies ( 2 ≤ n ≤  1,000) . The next line contains 2n space separated integers, the x and y coordinates of each colony (0 ≤ x, y ≤ 106) colonies are given in increasing order of their x coordinates. You can assume that no two colonies have the same x coordinates.\n\nFor each test case, print on a single line, a single number representing the minimum total length of force fields needed to cover all colonies, rounded to six decimal digits.\n\n"},{"iden":"input","content":"The first line contains one integer T, the number of test cases. Each test case consists of two lines, the first one contains an integer n, the number of colonies ( 2 ≤ n ≤  1,000) . The next line contains 2n space separated integers, the x and y coordinates of each colony (0 ≤ x, y ≤ 106) colonies are given in increasing order of their x coordinates. You can assume that no two colonies have the same x coordinates."},{"iden":"output","content":"For each test case, print on a single line, a single number representing the minimum total length of force fields needed to cover all colonies, rounded to six decimal digits."},{"iden":"examples","content":"Input330 2 1 1 2 230 0 1 1 2 040 0 1 100 2 1 3 100Output2.0000002.828427102.005000"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 1000 $, be the number of colonies.  \n- Let $ P = \\{(x_i, y_i)\\}_{i=1}^n $ be the set of colony coordinates, where $ x_1 < x_2 < \\dots < x_n $ and $ x_i, y_i \\in \\mathbb{R}_{\\geq 0} $.  \n\nA force field is a polyline connecting a subset of colonies such that:  \n- Each colony $ (x_i, y_i) $ is covered if there exists a force field polyline segment over $[x_j, x_k]$ with $ x_j \\leq x_i \\leq x_k $, and the polyline’s height at $ x_i $ is at least $ y_i $.  \n- The polyline is piecewise linear and monotonic in $ x $.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. For each test case:  \n   - $ 2 \\leq n \\leq 1000 $  \n   - $ 0 \\leq x_i, y_i \\leq 10^6 $  \n   - $ x_1 < x_2 < \\dots < x_n $  \n   - All $ x_i $ are distinct.  \n\n**Objective**  \nFind the minimum total Euclidean length of one or more non-overlapping (in $ x $-projection) polylines connecting subsets of colonies such that every colony $ (x_i, y_i) $ lies on or below the polyline over its $ x $-interval.  \n\nThe optimal solution is the minimum-length polygonal chain from $ (x_1, y_1) $ to $ (x_n, y_n) $ that lies above all intermediate points $ (x_i, y_i) $, i.e., the **upper convex hull** of the point set $ P $.  \n\nThus, compute the total length of the upper convex hull of $ P $.","simple_statement":"You are given n colonies on Mars, each at point (x_i, y_i), with x-coordinates in increasing order. You must cover all colonies with one or more straight-line force fields (each connecting two colonies). A colony is covered if it lies on or below the force field line between two endpoints. Find the minimum total length of force fields needed to cover all colonies.","has_page_source":false}