Авторы задачи: Владислав Власов и Даниил Орешников, разработчик: Арсений Кириллов
Заметим следующий факт: если существует круг радиуса $$$r$$$, покрывающий половину точек, то существует и круг того же радиуса, покрывающий половину точек, на границе которого лежат хотя бы две из данных точек. Это можно доказать следующим образом: рассмотрим такой круг, будем двигать его в какую-либо сторону, пока он не коснется одной из точек. Затем будем вращать его относительно этой точки, пока он впервые не коснется второй. Поскольку мы рассмотрели первые моменты касания, то все точки, которые были внутри, остались внутри.
Сделаем двоичный поиск по ответу — с помощью него угадаем радиус искомого круга. Для того, чтобы проверить, существует ли окружность радиуса $$$r = \frac{l + r}{2}$$$, покрывающая хотя бы половину точек, переберем пару точек, на которые она будет опираться (выше доказано, что достаточно перебрать только окружности, опирающиеся хотя бы на пару точек из множества). Для каждой фиксированной пары точек существует не более двух способов опереть на них окружность, а для каждого из этих двух способов можно за время $$$\mathcal{O}(n)$$$ найти количество точек, попадающих внутрь соответствующей окружности. Достаточно просто найти ее центр, и для каждой точки определить, правда ли, что расстояние от нее до центра не превосходит $$$r$$$.
Таким образом, получаем решение, работающее за время $$$\mathcal{O}(n^3 \cdot \log(10^{15}))$$$, что при аккуратной реализации проходило все тесты.