{"raw_statement":[{"iden":"statement","content":"Yesterday a strong storm hit the city, destroying many of the animals’ stables. Unfortunately *Bakkar's* little cute goat (*Rasheda*) was not lucky, and her zeriba (stable) was also destroyed by the storm. \n\n*Bakkar* is now searching for a better place for *Rasheda*, so he decided to buy a new piece of land to build *Rasheda*’s zeriba on it. The land owner only sells circular pieces of land. *Bakkar* has only a little amount of money to buy land and build the zeriba on it. Fortunately *Bakkar* managed to recover most of the wooden walls of the old zeriba, so he will use them to build the new one without buying new walls. To minimize the amount of money spent, *Bakkar* has to buy the smallest piece of land that can enclose the zeriba he is building.\n\nTo build the zeriba *Bakkar* uses the following strategy; using the _*N*_ walls recovered *Bakkar* would construct a non-degenerate convex polygon to build the zeriba. For construction purposes the walls of the new zeriba must be in the same order as they were in the old one. \n\nNow given the *N* lengths of the walls recovered, *Bakkar* will construct the zeriba so that it is a non-degenerate convex polygon with *N* sides, using the same order of the given walls. *Bakkar* then needs to know the radius of the smallest circle that can surround the entire polygon.\n\nAs you are a geometry lover, *Bakkar* called you to ask for you help. He will tell you the lengths of the walls then you would tell him the radius of the minimum circle that can enclose the zeriba if it is possible to construct a non-degenerate convex polygon using the sides. If it is not possible you would tell him that it's impossible.\n\nP.S.: A convex polygon is a polygon that has no angles pointing inwards. More precisely, no internal angle can be more than . A non-degenerate polygon is a polygon with a non-zero area.\n\nThe above figure illustrates a possible configuration of the first sample input in which there are 5 walls with lengths 5,5,2,3 and 1 respectively.\n\nYour program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  100). Followed by *T* test cases, each test case start with a single integer *N*, the number of walls recovered (3  ≤  *N*  ≤  1000). Following this, there are *N* space-separated positive integers, representing the length of each wall in anti-clockwise order. The length of each wall will not be more than 1000.\n\nFor each test case print a single line containing \"Case n:\" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a single real number representing the radius of the smallest circle the zeriba can fit in. Each output must be rounded to the nearest 0.0001 and must be printed with exactly four digits after the decimal point. If you can't form a convex polygon from the given walls just print \"can't form a convex polygon\" (without the quotes).\n\n"},{"iden":"input","content":"Your program will be tested on one or more test cases. The first line of the input will be a single integer *T*, the number of test cases (1  ≤  *T*  ≤  100). Followed by *T* test cases, each test case start with a single integer *N*, the number of walls recovered (3  ≤  *N*  ≤  1000). Following this, there are *N* space-separated positive integers, representing the length of each wall in anti-clockwise order. The length of each wall will not be more than 1000."},{"iden":"output","content":"For each test case print a single line containing \"Case n:\" (without the quotes) where n is the test case number (starting from 1) followed by a single space, then a single real number representing the radius of the smallest circle the zeriba can fit in. Each output must be rounded to the nearest 0.0001 and must be printed with exactly four digits after the decimal point. If you can't form a convex polygon from the given walls just print \"can't form a convex polygon\" (without the quotes)."},{"iden":"examples","content":"Input255 5 2 3 135 1 1OutputCase 1: 2.9039Case 2: can't form a convex polygon"}],"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\\} $:  \n- Let $ N_k \\in \\mathbb{Z} $ be the number of walls.  \n- Let $ L_k = (l_{k,1}, l_{k,2}, \\dots, l_{k,N_k}) $ be a sequence of positive real numbers representing the lengths of the walls in anti-clockwise order.\n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 3 \\le N_k \\le 1000 $  \n   - $ 1 \\le l_{k,i} \\le 1000 $ for all $ i \\in \\{1, \\dots, N_k\\} $  \n3. A non-degenerate convex polygon can be formed **if and only if** the sum of the lengths of any $ N_k - 1 $ sides is greater than the length of the remaining side:  \n   $$\n   \\forall j \\in \\{1, \\dots, N_k\\}, \\quad \\sum_{\\substack{i=1 \\\\ i \\ne j}}^{N_k} l_{k,i} > l_{k,j}\n   $$\n\n**Objective**  \nIf the polygon cannot be formed, output `\"can't form a convex polygon\"`.  \nOtherwise, compute the radius $ R_k $ of the **smallest enclosing circle** of the convex polygon with side lengths $ L_k $ in fixed cyclic order.  \nThis radius equals the **circumradius** of the cyclic polygon formed by the given side lengths in order, if such a cyclic polygon exists.  \n\nFor a cyclic convex polygon with given side lengths in fixed order, the circumradius $ R $ is the unique value satisfying:  \n$$\n\\sum_{i=1}^{N_k} \\arcsin\\left( \\frac{l_{k,i}}{2R} \\right) = \\pi\n$$  \nwith $ R > \\max_i \\left( \\frac{l_{k,i}}{2} \\right) $.  \n\nCompute $ R_k $ numerically to satisfy the above equation, rounded to four decimal places.","simple_statement":"Given N wall lengths, find the radius of the smallest circle that can enclose a convex polygon formed by using all walls in given order. If no such polygon can be formed, print \"can't form a convex polygon\".","has_page_source":false}