{"raw_statement":[{"iden":"statement","content":"You are given N segments in the xOy plane. Find the shortest closed broken line that contains all the given segments. A closed broken line is defined as a series of segments A[1 - A[2]], A[2 - A[3]] ... A[K - 1 - A[K]], A[K - A[1]], where A is an array of points on the plane. The line can intersect itself.\n\nThe first line contains T, the number of tests to follow. Then T tests follow. For each test, the first line contains an integer N(), followed by N lines, each describing a line segment by giving 4 real numbers, the x and y coordinates of the first end of the segment, and then the x and y coordinates of the second end of the segment.\n\nYour output file should contain T real numbers, representing the minimum length of the shortest closed broken line containing all the line segments. Your output should have a precision of 1.e - 6.\n\n"},{"iden":"input","content":"The first line contains T, the number of tests to follow. Then T tests follow. For each test, the first line contains an integer N(), followed by N lines, each describing a line segment by giving 4 real numbers, the x and y coordinates of the first end of the segment, and then the x and y coordinates of the second end of the segment."},{"iden":"output","content":"Your output file should contain T real numbers, representing the minimum length of the shortest closed broken line containing all the line segments. Your output should have a precision of 1.e - 6."}],"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 $ k \\in \\{1, \\dots, T\\} $, let $ N_k \\in \\mathbb{Z} $ be the number of line segments, and let $ S_k = \\{ \\overline{p_{i}^{(k)} q_{i}^{(k)}} \\mid i = 1, \\dots, N_k \\} $ be the set of segments, where $ p_i^{(k)}, q_i^{(k)} \\in \\mathbb{R}^2 $ are the endpoints of the $ i $-th segment.\n\n**Constraints**  \n1. $ 1 \\le T \\le \\text{some bound} $ (not specified, but assumed finite)  \n2. For each $ k $, $ N_k \\ge 1 $, and each segment is defined by two distinct points in $ \\mathbb{R}^2 $.  \n\n**Objective**  \nFor each test case $ k $, find the minimum total length of a closed polygonal chain $ A^{(k)} = (v_1, v_2, \\dots, v_m, v_1) $ such that:  \n- Each segment $ \\overline{p_i^{(k)} q_i^{(k)}} \\in S_k $ is entirely contained in the union of the edges of the chain.  \n- The chain may self-intersect.  \n- The length is $ \\sum_{j=1}^{m} \\| v_{j+1} - v_j \\| $, with $ v_{m+1} = v_1 $.  \n\nCompute:  \n$$\nL_k = \\min \\left\\{ \\sum_{j=1}^{m} \\| v_{j+1} - v_j \\| \\;\\middle|\\; \\bigcup_{j=1}^{m} \\overline{v_j v_{j+1}} \\supseteq \\bigcup_{i=1}^{N_k} \\overline{p_i^{(k)} q_i^{(k)}} \\right\\}\n$$\n\nOutput $ L_k $ for each test case $ k $, with precision $ 10^{-6} $.","simple_statement":"Find the shortest closed loop that passes through all given line segments.","has_page_source":false}