22068번 - Палочки и Шарниры 스페셜 저지다국어

Гриша и Дима играют со своим конструктором. В конструкторе есть детали двух видов: палочки и шарниры. Каждый шарнир может либо заканчивать цепочку, либо соединять две палочки, при этом палочки могут вращаться как угодно относительно этого соединения. Назовем конструкции, которые можно получить из этих деталей цепочками. Таким образом, если взять n палочек и n + 1 шарнир, то можно получить цепочку, которую можно свернуть в ломаную, ребрами которой являются палочки, а вершинами — шарниры. При этом ребра ломаной могут пересекаться и накладываться. Гриша и Дима всегда выкладывают цепочки на столе, поэтому все рассматриваемые в этой задаче ломаные расположены на плоскости.

На рисунке приведен пример цепочки. Шарниры пронумерованы в порядке обхода вдоль цепочки.

Дима взял n палочек и n + 1 шарнир и составил из них цепочку. Гриша же задался вопросом: если ввести декартову систему координат с центром в первом шарнире, то в окружность какого минимального радиуса с центром в начале координат можно будет поместить всю цепочку?

В окружность можно поместить цепочку если ее можно свернуть так, чтобы вся полученная ломаная находилась внутри или на границе окружности.

На рисунке приведен пример окружности, в которую можно поместить данную цепочку.

Ваша задача состоит в том, чтобы по длинам палочек в цепочке определить наименьший радиус окружности, в которую можно поместить эту цепочку. Размерами шарниров в этой задаче следует пренебрегать.

Первая строка содержит целое положительное число t — число тестовых примеров во входных данных. Далее следуют описания тестовых примеров.

Каждый тестовый пример описывается двумя строками. Первая строка содержит одно целое положительное число n (1 ≤ n ≤ 10⁵) — количество палочек в цепочке. Вторая строка содержит n целых положительных чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁴) — длины палочек в цепочке в том порядке, в котором они соединены.

Гарантируется, что сумма значений n по всем тестовым примерам не превышает 10⁵.

Выведите t строк. Для каждого тестового примера выведите радиус минимальной окружности, в которую можно поместить данную цепочку, с абсолютной погрешностью не больше 10⁻⁶.