У Джеймса Бонда, любимого секретного агента Джонни, новая миссия. Есть $$$n$$$ вражеских баз, каждая из которых задана своими координатами, так что мы можем рассматривать их как точки на плоскости.
Базы могут общаться друг с другом, посылая сигнал, который является лучом, из выбранной точки в направлении начала координат или в противоположном направлении. Исключением является центральная база, расположенная в начале координат. Она может посылать сигнал в любом направлении.
Когда какие-то две базы хотят коммуницировать, существует два возможных сценария. Если они лежат на одной прямой с началом координат, одна из них посылает сигнал непосредственно второй. Иначе, из первой базы сигнал посылается на центральную, и оттуда — на вторую. Обозначим расстоянием между двумя базами суммарное Евклидово расстояние, которое сигнал, посланный между ними, должен пройти.
Бонд может повредить все, кроме некоторых $$$k$$$ баз, которые он может выбрать на свое усмотрение. Поврежденная база не может посылать или получать сигнал напрямую, но все еще может передавать его между двумя работающими базами. В частности, Джеймс может повредить центральную базу, и сигнал все еще может быть послан между любыми двумя неповрежденными базами, как и раньше, и расстояние между ними останется неизменным. Какова максимальная сумма расстояний между всеми парами оставшихся баз, которую 007 может достичь, уничтожив ровно $$$n - k$$$ баз?
Первая строка содержит два целых числа $$$n$$$ и $$$k$$$ $$$(2 \leq k \leq n \leq 5 \cdot 10^5)$$$ — количество баз и количество баз, которое должно остаться, соответственно.
Каждая из следующих $$$n$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ $$$(-10^9 \leq x, y \leq 10^9)$$$, $$$i$$$-я строка содержит координаты $$$i$$$-й базы. Гарантируется, что никакие две точки не совпадают и что одна из точек равна $$$(0, 0)$$$.
Вы должны вывести одно число — максимальную возможную сумму расстояний между всеми парами некоторых $$$k$$$ из баз. Ваш ответ будет считаться правильным, если его абсолютная или относительная погрешность не превышает $$$10^{-6}$$$.
6 2 0 0 1 1 2 2 3 3 0 1 0 2
6.24264069
6 5 0 0 1 1 2 2 3 3 0 1 0 2
32.62741700
13 10 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 0 -2 0 1 0 2
237.00000000
10 5 2 2 4 4 3 5 6 10 0 5 0 0 5 0 10 0 0 10 4 7
181.52406315
В первом примере, в оптимальном решении Бонд не разрушает базы с номерами $$$4$$$ и $$$6$$$ (помечены оранжевым):
Следующая иллюстрация показывает оптимальное решение для второго примера. Следующие базы не разрушены: $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$ (помечены оранжевым).
Оптимальное решение для третьего теста изображено на иллюстрации. Только базы с номерами $$$3$$$, $$$4$$$ и $$$5$$$ разрушены. Снова, не разрушенные базы помечены оранжевым.
