Задача №114033. Колонизация
Давным-давно в далекой, далекой галактике на одной очень отдаленной планете стало слишком много людей, и они решили начать колонизацию. Не долго думая, они выбрали своей первой жертвой самый ближайший для них спутник — Луну.
На Луну на огромных шаттлах завезли N автономных модулей, чтобы поселить в них людей. Каждый модуль представляет собой купол из бионического стекла, имеющий форму круга радиуса R i . Но вдруг оказалось, что эти модули не совсем автономные: пришлось соединить их переходами, причем переходы можно построить только в случае, если купола стоят вплотную друг к другу (т.е. ограничивающие их окружности касаются внешним образом).
Итак, нашим космонавтам требуется построить лунную базу, то есть расставить модули так, чтобы между любыми двумя куполами был переход, и вычислить площадь получившейся базы. Но важно заметить, что площадью базы считается не только площадь под самими модулями, но и та область, в которую нельзя попасть, не проходя через купол.
Это заселение продолжалось многие годы, и затем, как и на старой планете, на Луне стало слишком мало места, поэтому люди решили достраивать базы. Они придумали в базу из трёх модулей добавлять четвёртый, если он достаточно мал, чтобы уместиться между тремя другими куполами. И естественно им необходимо построить новые переходы, для этого новый модуль должен стоять вплотную к трём другим. Но нужно знать радиус этого четвертого купола, чтобы потом построить его на специальной М-фабрике.
На рисунке окружностями схематично показаны модули, серым обозначена площадь базы, синими черточками — переходы между модулями, красным — искомый новый модуль для достройки.
В первой строке входных данных содержится число N — количество куполов ( 1 ≤ N ≤ 1000 ). В следующей строке содержатся N целых чисел — радиусы куполов (каждый радиус является натуральным числом и не превосходит 1000). В случае N = 3 в последней строке может также содержаться слово «INSERT».
В случае, если построить базу требуемым образом невозможно, выведите - 1 . В противном случае выведите искомую площадь. В случае, если N = 3 и в последней строке содержалось слово «INSERT», то в следующей строке необходимо вывести искомый радиус четвертого купола. Ваш ответ будет считаться верным, если его абсолютная или относительная погрешность не будет превосходить 10 - 6 .
Тесты к этой задаче состоят из четырёх групп:
- Тесты 1-3. Тесты из условия, оцениваются в 0 баллов.
- Тесты 4-13. В тестах этой группы N ≤ 3 , при этом искать радиус четвертого купола не требуется. Эта группа оценивается в 20 баллов.
- В тестах этой группы не требуется искать радиус четвертого купола. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
- В тестах этой группы N = 3 . Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы. Тестирование на тестах каждой группы производится только в случае прохождения всех тестов из всех предыдущих групп, за исключением тестов из условия.
3 1 2 3
44.4465535613
4 12 1 12 3
940.0432014879
3 2 8 8 INSERT
417.7969784391 0.6666666667