DK
У тебя радиус не дан
Size: a a a
2020 March 07
DK
Надо найти минимальный радиус чтобы покрыть К точек
KK
Ну и, зачем мне бинпоиск?
KK
Мне нужно перебрать онои 3 точки
KK
Там 60 точек, я за куб переберу три и возьму центр
Я бы, кстати, там еще, желательно, поверх этого навернул градиентный спуск
KK
Да и вообще это выглядит как слау
KK
Слау вида
1 * X_i + 0 = x_i
1 * X_i + 0 = x_i
... c_i раз
0 + 1 * Y_i = y_i
... c_i раз
1 * X_i + 0 = x_i
1 * X_i + 0 = x_i
... c_i раз
0 + 1 * Y_i = y_i
... c_i раз
KK
Матрица 6000 * 2, изи ищем псевдообратную, т.к. там 2*2, умножаем на нее, получаем точки, считаем ответ)
KK
А, чет я тупой, какие матрицы, там точек то k нужно, ок
KK
А так я просто среднеарифметическое с весами найду
KK
Есть, кстати, k диаграма вороного
KK
Плди можно обобщить ее и на веса
KK
А когда она найдена, то там уже просто надо среднее арифметическое по каждой области найти
A
В advent of code бинарным поиском решалось так - сначала находим такой круг, которым просто можно накрыть ваще все. Потом делим его на части (в половину радиуса) и находим, какая из частей накрывает больше других. Но там метрика была x+y, там это было чуток проще
A
и точки были целочисленные
K
Есть за o(n) решение с рандомом
https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек
https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек
Спасибо
K
какие лица, привет :)
RK
какие лица, привет :)
Привет
ПК
Кто умеет фибхип реализовывать?
C
Кто умеет фибхип реализовывать?