= Численное интегрирование

Дана функция $y = f(x)$. Хотим посчитать $integral_a^b f(x)$.

== Метод Монте-Карло

Работает, но сходится медленно

Возьмем $sin(x), x in [0, pi]$.

Будем генерировать точки в прямоугольнике $x in [0, pi]; y in [0, pi]$ и
смотреть, сколько попало под график.

== Детерминированный метод

Разбиваем отрезок на равные кусочки:
$ a = x_0 < x_1 < ... < x_n = b $
$ x_(i + 1) - x_i = h = (b - a) / n $

Один кусок ($x in [x_i, x_(i + 1)]$) --- криволинейная трапеция. Её можно
приближать разными фигурами:
- Прямоугольником:
    - $S = h dot f(x_i)$ --- метод левых прямоугольников
    - $S = h dot f(x_(i + 1))$ --- метод правых прямоугольников
    - $S = h dot f((x_i + x_(i + 1)) / 2)$ --- метод средних прямоугольников
- Трапецией:
    - $S = h/2 (f(x_i) + f(x_(i + 1)))$
- Криволинейной трапецией (с параболой сверху):
    - $S= h/6 (f(x_i) + 4f((x_i + x_(i + 1)) / 2) + f(x_(i + 1))$ --- формула
      Симпсона

У формулы Симпсона сходимость на два порядка выше

=== Пример

Ищем площадь круга:
$ (x - 1)^2 + (y - 5)^2 = 9 $

Разбиваем на две полуокружности: верхнюю ($f_1 (x)$) и нижнюю ($f_2 (x)$)

$ S = integral_(-2)^4 f_1 - f_2 (x) d x $

== Сетки переменной плотности

Интегрируем верхнюю половину окружности. Будем использовать метод левых
прямоугольников. Если разрезать на четыре части, то два центральные кусочка
дают хорошее приближение, а два крайних --- очень плохое.

Вывод: сетка с постоянным шагом --- часто плохой вариант.

Алгоритм:
- Делим на несколько частей
- Проверяем, на каких кусках получили хорошее приближение, а на каких плохое.

    Для этого всё же измельчаем сетку в этом месте и проверяем, сильно ли
    изменилось приближение. Если слабо, то приближение хорошее:
    $ abs(S_1 - S_2) < epsilon $
    
- Там, где получили плохое приближение, запускается от него рекурсивно.

Метод хорошо сходится, но мы плохо можем оценивать приближение.

== Задача (похожая на 2-ую и 3-ю из контеста)

Есть набор фигур на экране. Найти площадь объединения

Методы решения (по увеличению эффективности):
+ *Монте-Карло*: плохо сходится
+ *Сетка*:

    Разрежем на сеточку (по вертикали и горизонтали).
    Смотрим на центр: считаем, что если входит центр, то входит весь
    прямоугольник

+ *Квадродерево*:

    - Режем на сетку. Смотрим на каждый квадратик.
    - Если квадратик заполнен полностью или полностью пустой, то сразу добавляем
        его в ответ
    - Иначе (если заполнен частично), то продолжаем рекурсивно.
    - Останавливаемся, если получили квадратик площади меньше $epsilon$

+ *Вертикальные полосы переменной плотности + Сканлайн*

    - Режем на полоски, которые дают элементарные элементарные
        огибающие. Можно порезать и сильнее.

    - Каждая фигура идет от начала до конца полосы (то есть по горизонтали начинается и
        заканчивается либо на границе полосы, либо вне её).

    - Внутри каждой полосы, заменяем каждую фигуру на прямоугольник, дальше
        сканлайном ищем площадь пересечения.

    - Потом делим вертикальную линию пополам, проверяем хорошее ли получилось
        приближение, если плохое, запускаемся дальше
