Если делать "руками", то я бы не так решал. Фиксируем

и полагаем

.
Функционал

легко минимизируется по

. Для этого надо просто найти медиану в множестве

.
Ну а дальше, что-нибудь типа делением пополам для оптимизации по

.
Сложность получится типа

,
где

- допустимая погрешность. Ну а если чуть постараться, то и от

можно избавиться.
По-моему дешево и сердито.