T
Бинарное возведение на емаксе есть
Size: a a a
2020 March 06
A
Можете покидать теории по матрицам? Недавно на школьной олимпе встретилось бинарное возведение матрицы, вообще офигел с этого, когда узнал
Умножение матриц ассоциативно, а координаты результирующего вектора (после умножения на матрицу) равны линейным комбинациям координат исходного с соответствующими коэффициентами из матрицы (см. формулу умножения матриц).
Вроде этого достаточно для понимания трюка
Вроде этого достаточно для понимания трюка
A(
Можете покидать теории по матрицам? Недавно на школьной олимпе встретилось бинарное возведение матрицы, вообще офигел с этого, когда узнал
достаточно знать что если есть состояние, значение которого определяется как линейная комбинация предыдущих состояний (то есть current = a*prev+b*prev_prev+c*prev_prev_prev ...) то это можно выразить как умножение вектора на матрицу, ну а это в свою очередь повзоляет быстро подносить ее в степень
SF
Круг радиуса r лежит в круге радиуса R тогда и только тогда когда расстояние между центрами <= R-r
A
да
VM
Наверное, в качестве центра можно попробовать взять все центры описанных окружностей и для каждого из них посчитать ответ. Потом найти максимум, это и будет ответом
A
описанных вокруг чего?
VM
Вокруг тройки точек
VM
Мы перебираем все тройки
K
на самом деле достаточно пары и окружности радиуса R-r
A
можно свести эту задачу к одной из последнего advent of code
K
оккружностей 10^4, и для каждой из них проверить 100 точек
K
10:6
A
заменить окружности "городов" на окружности "если бутылка упадет тут внутри, то разнесет все" и искать точку пересечения максимального числа таких окружностей
E
Вот тут несколько решений этой задачи. Одно другого быстрее. Но для тимуса пойдет и самое тривиальное за O(N^3). https://www.quora.com/What-is-an-algorithm-for-enclosing-the-maximum-number-of-points-in-a-2-D-plane-with-a-fixed-radius-circle
A
в advent of code это решали бинарным поиском
2020 March 07
K
А как по множеству точек на плоскости найти окружность минимального радиуса, их содержащую?
K
Вроде знал, но забыл
AD
найти 2 самые удаленные?