Геометрия (дополнение)

  1. Проверка, лежит ли точка внутри простого многоугольника за O(N) горизонтальным лучом.
  2. Решение той же задачи для K запросов в Offline за O((N+K)logN)
  3. Пересечение полуплосокстей, случай угла больше Пи. Пересечение двух выпуклых за O(NlogN).
  4. Пересечение выпуклых за O(N) (метод 4-х указателей)
  5. Сумма (и разность) Минковского за O(N) (2 указателя)
  6. Проверка, пересекается ли отрезок с многоугольником (сперва найти пересечение с прямой, затем параметризовать оба отрезка)

Про Гаусса

  1. Вероятность (с какой вероятоностью попадем из A в B)
  2. Матожидание (какой матожидание числа шагов от A до B)
  3. Случай разреженной матрицы. За сколько работает Гаусс: O(N3)? O(N2)? O(N)?
  4. Not read Добавление вектора в базис за O(N2).

Про простые числа

  1. Проверка на простоту за O(logN) (тест Миллера-Рабина)
  2. Разложение на множители за O(N1/4) (эвристика Полларда)
  3. Поиск количесвта простых чисел от 1 до N за O(N2/3)
    1. Phi(n, x) = Phi(n, x-1) - Phi(n/(x-1),x-1)
    2. Phi(n, 1) = n
    3. Phi(n, x) = 0 (для x > n)
    4. Phi(n, x) считается специальным способом в Offline для n <= M
    5. Берем M = n2/3