CD
А как по множеству точек на плоскости найти окружность минимального радиуса, их содержащую?
За сколько?
Size: a a a
2020 March 07
CD
За куб там легко
CD
Быстрее придется с выпуклой шаманировать, видимо
CD
За куб проверить пары как диаметр и пары как стороны треугольника
MB
А как по множеству точек на плоскости найти окружность минимального радиуса, их содержащую?
Сначала пишется перебор за куб.
Потом надо пошафлить точки.
Если перебор из п.1 был хорошим, то теперь он будет работать за линию
Потом надо пошафлить точки.
Если перебор из п.1 был хорошим, то теперь он будет работать за линию
MB
Стоп, или речь про именно окружность?
DK
Нифига вы какие способы знаете
DK
Предлагаю двумерный тернарный поиск
KK
А как по множеству точек на плоскости найти окружность минимального радиуса, их содержащую?
Есть за o(n) решение с рандомом
https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек
https://neerc.ifmo.ru/wiki/index.php?title=Минимальная_охватывающая_окружность_множества_точек
KK
Нифига вы какие способы знаете
Это стандартная штука)
DK
Это стандартная штука)
Двумерный тернарный поиск является стандартной штукой, а это - нет
DK
Это стандартная штука)
Ты, кстати, знал, что есть стандартная штука, чтобы определить, можно ли провести окружность радиуса R такую, что она охватывает не менее K заданных точек?
https://atcoder.jp/contests/abc157/tasks/abc157_f
https://atcoder.jp/contests/abc157/tasks/abc157_f
KK
Ты, кстати, знал, что есть стандартная штука, чтобы определить, можно ли провести окружность радиуса R такую, что она охватывает не менее K заданных точек?
https://atcoder.jp/contests/abc157/tasks/abc157_f
https://atcoder.jp/contests/abc157/tasks/abc157_f
Там 60 точек, я за куб переберу три и возьму центр
DK
Там 60 точек, я за куб переберу три и возьму центр
Ты не влезешь в TL
KK
Ты не влезешь в TL
Шо?
KK
60^4 не лезет в тл?
DK
60^4 не лезет в тл?
У тебя еще логарифм сверху
DK
Ты задачу читал? Там бинпоиск по радиусу
KK
У тебя еще логарифм сверху
Где?