У Джеймса Бонда, любимого секретного агента Джонни, новая миссия. Есть \(n\) вражеских баз, каждая из которых задана своими координатами, так что мы можем рассматривать их как точки на плоскости.
Базы могут общаться друг с другом, посылая сигнал, который является лучом, из выбранной точки в направлении начала координат или в противоположном направлении. Исключением является центральная база, расположенная в начале координат. Она может посылать сигнал в любом направлении.
Когда какие-то две базы хотят коммуницировать, существует два возможных сценария. Если они лежат на одной прямой с началом координат, одна из них посылает сигнал непосредственно второй. Иначе, из первой базы сигнал посылается на центральную, и оттуда — на вторую. Обозначим расстоянием между двумя базами суммарное Евклидово расстояние, которое сигнал, посланный между ними, должен пройти.
Бонд может повредить все, кроме некоторых \(k\) баз, которые он может выбрать на свое усмотрение. Поврежденная база не может посылать или получать сигнал напрямую, но все еще может передавать его между двумя работающими базами. В частности, Джеймс может повредить центральную базу, и сигнал все еще может быть послан между любыми двумя неповрежденными базами, как и раньше, и расстояние между ними останется неизменным. Какова максимальная сумма расстояний между всеми парами оставшихся баз, которую 007 может достичь, уничтожив ровно \(n - k\) баз?
Выходные данные
Вы должны вывести одно число — максимальную возможную сумму расстояний между всеми парами некоторых \(k\) из баз. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает \(10^{-6}\).
Примечание
В первом примере, в оптимальном решении Бонд не разрушает базы с номерами \(4\) и \(6\) (помечены оранжевым):
Следующая иллюстрация показывает оптимальное решение для второго примера. Следующие базы не разрушены: \(2\), \(3\), \(4\), \(5\), \(6\) (помечены оранжевым).
Оптимальное решение для третьего теста изображено на иллюстрации. Только базы с номерами \(3\), \(4\) и \(5\) разрушены. Снова, не разрушенные базы помечены оранжевым.
