1:30 Работаем на декартовой плоскости: точка задаётся двумя координатами, множество всех точек обозначают $\mathbb R^2$. Вектор — это направление (изменение $\Delta x,\Delta y$): у него нет начала, его можно выпускать из любой точки. Точка — это вектор, выходящий из начала координат; различие между точкой и вектором мы дальше не делаем.
2:11 Векторы удобны тем, что многие задачи не зависят от положения фигуры: например, треугольник можно задать тремя сторонами-векторами.
4:54 Скалярное произведение (обозначим $\cdot$) двух векторов — число, а не вектор:
5:34 Первая формула — удобна для вычислений в координатах (и обобщается на любую размерность), вторая показывает геометрический смысл ($\theta$ — угол между векторами).
7:40 Главное применение — классификация угла без тригонометрии: знак скалярного произведения совпадает со знаком $\cos\theta$. Если $v\cdot u>0$ — угол острый ($<90^\circ$), если $=0$ — прямой, если $<0$ — тупой. Всё считается в целых числах, не нужны арктангенсы.
8:22 Векторное (псевдоскалярное) произведение двух векторов на плоскости — тоже число:
9:44 Формула несимметрична: при перестановке $u$ и $v$ знак меняется. В C++ его удобно обозначать % (приоритет выше, чем у +, как у умножения; у ^ приоритет низкий). Абсолютная величина $|u\times v|$ — площадь параллелограмма, натянутого на $u$ и $v$; площадь треугольника — половина этого. Для целых координат площадь треугольника — полуцелое число.
11:46 Это важнейшее соотношение геометрии. Если $u\times v=0$, векторы коллинеарны (угол $0$ или $180^\circ$) — коллинеарность проверяется бесплатно. Иначе знак показывает, в какую сторону кратчайший поворот от $u$ к $v$:
14:29 Для проверки перпендикулярности используют скалярное произведение: $v\perp u\iff v\cdot u=0$. Перпендикулярный вектор находится «бесплатно» — повернуть на $90^\circ$ против часовой стрелки: $(x,y)\mapsto(-y,x)$. Проверка: $x(-y)+y\,x=0$. (Четыре таких поворота возвращают исходный вектор — удобная проверка себя.)
15:09 Хранить точки в pair<int,int> или в отдельных переменных «бесконечно больно». Заводим структуру точки и перегружаем операции:
struct Point {
long long x, y;
Point operator+(Point o) const { return {x + o.x, y + o.y}; }
Point operator-(Point o) const { return {x - o.x, y - o.y}; }
Point operator*(long long k) const { return {x * k, y * k}; } // точка * число
long long operator*(Point o) const { return x * o.x + y * o.y; } // скалярное
long long operator%(Point o) const { return x * o.y - y * o.x; } // векторное
};
istream &operator>>(istream &in, Point &p) { return in >> p.x >> p.y; }Point operator*(long long k), то P * k работает, а k * P — нет (нужен отдельный оператор вне класса).long long; произведение двух таких величин в long long уже не помещается (поэтому при сравнении знаков берём знак, а не перемножаем).x и y отдельно), но удобны.19:16 Школьное $y=kx+b$ не описывает вертикальные прямые. Поэтому прямую задаём тремя числами $(A,B,C)$: точка $(x,y)$ лежит на прямой, если
20:38 Условие $(A,B)\ne(0,0)$ необходимо: иначе при $C=0$ подходят все точки плоскости, а при $C\ne0$ — ни одной. Прежнее $y=kx+b$ превращается в $kx-y+b=0$; вертикальная прямая — это $B=0$.
22:41 Вектор $\vec d=(-B,A)$ параллелен прямой: если $(x,y)$ на прямой, то $A(x-B)+B(y+A)+C=Ax+By+C=0$, т. е. $(x,y)+\vec d$ тоже на прямой. Вектор нормали $\vec n=(A,B)$ перпендикулярен $\vec d$ (поворот на $90^\circ$). Тогда уравнение прямой в компактной записи:
32:11 Интуиция: $\vec n$ задаёт «наклон» — какое семейство параллельных прямых, а константа $C$ — какую именно из этих параллельных прямых мы взяли.
28:07 По точкам $A,B$: направление $\vec d=B-A$, нормаль $\vec n=(-d_y,d_x)$, уравнение $\vec n\cdot X+C=0$ и подстановка точки $A$ даёт $C=-\vec n\cdot A$. В координатах: $A_{\text{коэф}}=A_y-B_y,\ B_{\text{коэф}}=B_x-A_x,\ C=A_xB_y-A_yB_x$ — то есть $C=A\times B$.
30:10 Дана прямая $(\vec n,C)$; найти точку и направление. Проведём перпендикуляр из начала координат — он идёт вдоль $\vec n$ и пересечёт прямую в точке $\lambda\vec n$. Подставляя: $\lambda\,(\vec n\cdot\vec n)+C=0\Rightarrow\lambda=-C/(A^2+B^2)$ (корень брать не нужно):
33:37 При параллельном переносе на $\vec m$ нормаль не меняется, меняется константа: $\vec n\cdot(X-\vec m)+C=0$, то есть новая константа $C'=C-\vec n\cdot\vec m$.
36:20 Зададим прямые параметрически: $A+t\,\vec u$ и $B+s\,\vec v$. Приравнивая, $A+t\vec u=B+s\vec v$. Умножим обе части векторно на $\vec v$: слагаемое с $s$ исчезает ($\vec v\times\vec v=0$):
37:48 Если $\vec u\times\vec v=0$, направления коллинеарны — прямые либо параллельны, либо совпадают (легко проверяется). В координатном виде — решение системы двух линейных уравнений $A_1x+B_1y+C_1=0$, $A_2x+B_2y+C_2=0$.
42:32 Проекция $H$ точки $P$ на прямую: $P-H$ параллелен $\vec n$, значит $H=P-t\vec n$. Подставив в уравнение прямой: $\vec n\cdot(P-t\vec n)+C=0\Rightarrow t=\dfrac{\vec n\cdot P+C}{|\vec n|^2}$ (нормаль ненулевая, делить можно). Расстояние — $|PH|=\dfrac{|\vec n\cdot P+C|}{|\vec n|}$.
44:34 Точка $Q$, симметричная $P$ относительно прямой: $H$ — середина $PQ$, поэтому $Q=2H-P$.
54:11 Нужно: $P$ лежит на $AB$. Во-первых, точка на прямой $AB$: $\vec{AP}\times\vec{AB}=0$ (коллинеарность). Но этого мало — $P$ может лежать на прямой вне отрезка. Поэтому дополнительно проверяют проекции на обе оси: $\min(A_x,B_x)\le P_x\le\max(A_x,B_x)$ и то же для $y$.
bool onSegment(Point a, Point b, Point p) {
return (b - a) % (p - a) == 0
&& min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x)
&& min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}55:33 Обе проекции проверять нужно: для горизонтальных/вертикальных отрезков одной недостаточно.
58:14 Случаев очень много; идём по шагам. Если отрезки пересекаются, то $C$ и $D$ не могут лежать строго по одну сторону от прямой $AB$: произведение знаков $\operatorname{sign}\bigl(\vec{AB}\times\vec{AC}\bigr)\cdot\operatorname{sign}\bigl(\vec{AB}\times\vec{AD}\bigr)\le0$ (и аналогично для прямой $CD$ и точек $A,B$). Эти проверки гарантируют пересечение прямой с отрезком; но отрезки могут не пересекаться, лёжа на одной прямой «врозь» — поэтому добавляют проверку, что проекции на оси пересекаются.
int sgn(long long v) { return (v > 0) - (v < 0); }
bool inter1(long long a, long long b, long long c, long long d) { // пересечение отрезков на оси
if (a > b) swap(a, b);
if (c > d) swap(c, d);
return max(a, c) <= min(b, d);
}
bool intersect(Point a, Point b, Point c, Point d) {
return inter1(a.x, b.x, c.x, d.x) && inter1(a.y, b.y, c.y, d.y)
&& sgn((b - a) % (c - a)) * sgn((b - a) % (d - a)) <= 0
&& sgn((d - c) % (a - c)) * sgn((d - c) % (b - c)) <= 0;
}double и проверить, что она на отрезках» даёт ошибки точности даже для $10^9$, а проверка знаков абсолютно точна.intersect сверена на всех «малых» случаях (координаты от $-4$ до $4$, включая вырожденные и коллинеарные) с независимой проверкой через параметры $t,u$ в рациональных числах.63:39 Пересечения луча с лучом, луча с отрезком рассматриваются аналогично (в презентации — разбор случаев; здесь пропущено). Если «луч» заменять очень длинным отрезком, придётся использовать более широкий тип (__int128), т. к. точки пересечения могут быть порядка $10^{18}$.
66:22 Окружность $\omega$ — центр $O$ и радиус $r$: все точки, находящиеся на расстоянии $r$ от центра, т. е. $(x-O_x)^2+(y-O_y)^2=r^2$ (в целых числах — без корня).
68:25 Находим расстояние $h$ от центра до прямой (через проекцию $H$). Если $h>r$ — пересечений нет; $h=r$ — касание (одна точка $H$); $h<r$ — две точки. По теореме Пифагора из прямоугольного треугольника $OHX$: $s=\sqrt{r^2-h^2}$, а точки пересечения — $H\pm s\,\dfrac{\vec d}{|\vec d|}$ (сдвиг вдоль прямой).
71:10 Если центры совпадают — вырожденный случай (вложены или совпадают). Иначе вычтем уравнения окружностей: $x^2+y^2$ сокращаются, и остаётся линейное уравнение — радикальная прямая, на которой лежат обе точки пересечения (через две точки проходит ровно одна прямая):
71:51 Остаётся пересечь любую из окружностей с этой прямой (формула предыдущего пункта работает и для касания).
73:14 Касательная к фигуре из точки — это угол, содержащий всю фигуру и наименьший из таких. Если точка внутри — касательных нет; на окружности — касательная одна; снаружи — две. Радиус в точку касания перпендикулярен касательной: $(T-O)\cdot(T-P)=0$. На лекции вывод прошёл «в координатах и не до конца»; вот полный вывод.
83:11 Площадь произвольного (в том числе невыпуклого) многоугольника $P_0P_1\dots P_{n-1}$, заданного обходом: суммируем ориентированные площади треугольников $OP_iP_{i+1}$ (с началом координат $O$):
long long area2(const vector<Point> &p) { // удвоенная площадь (целое число)
long long s = 0;
int n = p.size();
for (int i = 0; i < n; ++i) s += p[i] % p[(i + 1) % n];
return llabs(s);
}85:12 Почему это работает: инвариант — после добавления очередной вершины сумма равна ориентированной площади многоугольника $OP_0\dots P_i$ (с «замыканием» стороной $P_iO$ и $OP_0$); «лишние» треугольники с обратным знаком вычитаются. Последний шаг $P_{n-1}P_0$ замыкает контур, и остаётся площадь самого многоугольника. При координатах до $10^9$ по модулю удвоенная площадь не превосходит $\approx8\cdot10^{18}$ и ещё помещается в long long (для больших координат нужен __int128); на два делят только в конце, поэтому удобно хранить удвоенную площадь.
89:18 Нужно определить: точка внутри, снаружи или на границе. Границу проверяем примитивами (точка на отрезке). Для остального — несколько методов.
91:22 Выпустим из точки луч и посчитаем, сколько раз он пересекает границу: чётное — точка снаружи, нечётное — внутри (идя по лучу, мы входим и выходим из многоугольника, и в конце луча оказываемся снаружи). Подвох — горизонтальные стороны и проход луча через вершину; принято не считать пересечения со сторонами, лежащими на луче, и использовать полуоткрытое правило по $y$ (сторона считается пересечённой, если $y$ луча лежит в $[\min y,\max y)$ стороны).
// луч из q в направлении +x; poly — вершины по порядку, q не на границе
int cnt = 0;
for (int i = 0; i < n; ++i) {
Point a = poly[i], b = poly[(i + 1) % n];
if ((a.y > q.y) != (b.y > q.y)) { // сторона пересекает горизонталь y = q.y
long long c = (b - a) % (q - a);
if (b.y > a.y ? c > 0 : c < 0) cnt++; // пересечение правее q
}
}
bool inside = cnt & 1;96:09 Альтернатива: просуммировать ориентированные углы между векторами из точки в соседние вершины; если сумма равна $\pm2\pi$ — точка внутри, иначе (сумма $0$) — снаружи. Он работает с углами (atan2, вещественные числа), поэтому менее надёжен, а граница проверяется отдельно. Попытка заменить углы на площади («на букве Ш») не работает: площадь зависит от длин сторон, а нормированные углы — нет.
101:44 Расстояние между объектами — минимальное расстояние между их точками. До отрезка: если проекция $H$ точки на прямую попадает в отрезок, то ответ $|PH|$ (любая другая точка отрезка даёт гипотенузу, а она длиннее катета); иначе — расстояние до ближайшего конца отрезка. Проекция попадает на отрезок, если скалярные произведения $\vec{AB}\cdot\vec{AP}\ge0$ и $\vec{BA}\cdot\vec{BP}\ge0$.
double distPointSegment(Point a, Point b, Point p) {
if ((b - a) * (p - a) >= 0 && (a - b) * (p - b) >= 0) // проекция внутри отрезка
return fabs((double)((b - a) % (p - a))) / hypot(b.x - a.x, b.y - a.y);
return min(hypot(p.x - a.x, p.y - a.y), hypot(p.x - b.x, p.y - b.y));
}103:46 До многоугольника: если точка внутри (или на границе) — ответ $0$; иначе ближе всего какая-то сторона (отрезок от точки к внутренней точке пересечёт границу, причём ближе). Значит, ответ — минимум расстояний до всех сторон.
107:13 Касательная к многоугольнику из точки $P$ — наименьший угол с вершиной в $P$, содержащий весь многоугольник (если точка снаружи). Каждая сторона даёт ограничение: должна быть покрыта дуга на «окружности направлений» вокруг $P$; нужно найти дугу, содержащую все такие дуги (для выпуклого многоугольника сводится к двум вершинам, для которых можно искать за $O(\log n)$ — см. ниже). Обычно в задачах на касательные многоугольники выпуклые.
116:21 Практическая задача: рисуем многоугольник на экране-сетке; закрашиваем целые клетки. Сначала контур: идём по сторонам и закрашиваем клетки, пересекаемые стороной, за $O(n+P)$ ($P$ — число клеток на границе); на каждом шаге следующая клетка — соседняя (вверх или вправо, в зависимости от направления отрезка), её выбор определяется тем, какое пересечение «раньше». Здесь допустима потеря точности — пиксель-другой не страшен.
120:28 Для каждой строки $y$ закрашиваем отрезок от минимального до максимального $x$ — их находим при обходе границы. Время $O(S+n)$ ($S$ — площадь).
125:16 «От минимума до максимума» на невыпуклом многоугольнике ломается (например, буква «Е»). Вместо этого используем принцип чётности: в ограничивающем прямоугольнике (bounding box) на границе ставим единицу, затем идём по строкам слева направо, считаем префиксные xor — клетка закрашена, если слева было нечётное число границ. Варианты по памяти: $O(S_{\text{box}})$ памяти; либо для каждой строки хранить только $x$-координаты границы и сортировать (в том числе сортировкой подсчётом) — тогда память меньше, время $O(S\log S+n\log n)$.
132:09 Дано множество ненулевых векторов из начала координат; отсортировать против часовой стрелки, начиная с направления $+x$. Сортировка по полярному углу (atan2) вещественная; хотим в целых. Компаратор «$u<v$, если $u\times v>0$» не работает: он не транзитивен (при трёх векторах, расположенных так, что от $u$ к $v$ и от $v$ к $z$ меньше $180^\circ$, а от $u$ к $z$ больше, получится цикл).
134:12 Исправление: делим плоскость на две «половины» и сравниваем сначала по половине, затем внутри одной половины — по векторному произведению. Первая половина: $y>0$ или ($y=0$ и $x>0$); вторая — всё остальное. Векторы разных половин не сравниваем по произведению, так как «красный» и «синий» противоположные векторы дают $0$ — их не отличить.
int half(Point p) { return (p.y > 0 || (p.y == 0 && p.x > 0)) ? 0 : 1; }
bool byAngle(Point a, Point b) {
int ha = half(a), hb = half(b);
if (ha != hb) return ha < hb;
long long c = a % b;
if (c != 0) return c > 0; // a раньше b, если b — против часовой от a
return a * a < b * b; // коллинеарные: по длине (необязательно, для определённости)
}atan2 на случайных множествах целых векторов (ненулевых): порядок совпал.139:39 Дано множество точек вокруг начала координат; в нём стоит камера с углом обзора $90^\circ$. Нужно повернуть камеру так, чтобы в кадр попало как можно больше точек. Сортируем векторы по углу (предыдущий пункт) и идём двумя указателями по циклическому массиву: для каждого $l$ окно $[l,r]$ — максимальное, в котором угол от $v_l$ против часовой стрелки до $v_r$ не превышает $90^\circ$. Условие «угол $\theta\in[0^\circ,90^\circ]$» записывается через оба произведения: $v_l\cdot v_r\ge0$ и $v_l\times v_r\ge0$.
141:01 Одного скалярного произведения недостаточно: оно неотрицательно и при угле между $270^\circ$ и $360^\circ$, то есть цикл «замыкается» и приводит к неверным окнам; векторное произведение это отсекает.
// v — векторы, отсортированные по углу (byAngle), n = v.size()
int best = 0, r = 0;
for (int l = 0; l < n; ++l) {
if (r < l) r = l;
while (r + 1 - l < n && (v[l] * v[(r + 1) % n]) >= 0 && (v[l] % v[(r + 1) % n]) >= 0) r++;
best = max(best, r - l + 1); // число точек в кадре
}143:47 Выпуклая оболочка (convex hull) множества точек — минимальный по включению выпуклый многоугольник, содержащий все точки; все точки либо вершины, либо на границе, либо строго внутри. Она единственна: пересечение двух выпуклых многоугольников, содержащих точки, — снова выпуклый многоугольник, содержащий точки и не большей площади. Базовая идея алгоритмов — найти точку, точно лежащую на оболочке: самая нижняя (при равенстве — самая левая) точка, то есть минимум пары $(y,x)$.
149:57 Стоим в самой нижней точке. Следующая вершина оболочки при обходе против часовой стрелки — точка с наименьшим углом относительно текущего направления (при равных углах — самая дальняя). Повторяем, пока не вернёмся в начало. Время $O(nh)$, где $h$ — размер оболочки; в худшем случае $O(n^2)$. Сравнивать углы не нужно: все остальные точки лежат в одной полуплоскости от опорной стороны, поэтому достаточно знака векторного произведения.
// p — точки (без повторов); o — самая нижняя (левая из нижних)
vector<Point> hull = {};
Point cur = o;
do {
hull.push_back(cur);
Point nxt = (p[0] == cur) ? p[1] : p[0];
for (Point q : p) {
if (q == cur) continue;
long long c = (nxt - cur) % (q - cur);
if (c < 0 || (c == 0 && (q - cur) * (q - cur) > (nxt - cur) * (nxt - cur)))
nxt = q; // q «правее» nxt или на той же прямой, но дальше
}
cur = nxt;
} while (!(cur == o));153:19 Берём опорную (самую нижнюю) точку $P_0$, сортируем остальные по углу относительно неё (при равных углах — по возрастанию расстояния). Идём по порядку и поддерживаем в стеке оболочку просмотренного префикса. Новая точка по углу левее всей уже построенной оболочки, поэтому она точно будет вершиной, а из конца стека нужно выкинуть вершины, оказавшиеся после «касательной». Условие: пока $\vec{p_1p_2}\times\vec{p_2a}\le0$ (здесь $p_1,p_2$ — последние две точки стека, $a$ — новая), удаляем $p_2$; иначе кладём $a$.
// o — самая нижняя (левая из нижних); r — остальные точки
sort(r.begin(), r.end(), [&](Point a, Point b) {
long long c = (a - o) % (b - o);
if (c != 0) return c > 0; // по углу против часовой
return (a - o) * (a - o) < (b - o) * (b - o); // при равенстве — ближайшая первой
});
vector<Point> st = {o};
for (Point q : r) {
while (st.size() >= 2 && (st[st.size()-1] - st[st.size()-2]) % (q - st[st.size()-1]) <= 0)
st.pop_back(); // нестрого: коллинеарные вершины не нужны
st.push_back(q);
}161:33 Время $O(n\log n)$ на сортировку плюс $O(n)$ на проход (каждая точка удаляется не более одного раза). Условие $\le0$ делает выкидывание коллинеарных точек: с сортировкой «по расстоянию при равных углах» в начале алгоритма (несколько точек на первом луче) стек остаётся размера 2, в конце (несколько точек на последнем луче) каждая следующая более дальняя точка вытесняет предыдущую. Если использовать другое условие (например, сравнивать с $P_1$), могут остаться лишние вершины на границе.
184:14 Если отсортировать точки не по углу, а по координатам ($x$, при равенстве — $y$), то тот же проход со стеком строит нижнюю огибающую: ломаную от самой левой точки до самой правой, над которой лежат все точки. Тот же проход в обратном порядке (справа налево, второй стек) строит верхнюю огибающую (это то же самое, что повернуть плоскость на $180^\circ$). Склеив их (с отбрасыванием повторяющихся концов), получаем полную оболочку за $O(n)$ после сортировки.
vector<Point> hull(vector<Point> p) {
sort(p.begin(), p.end(), [](Point a, Point b) { return a.x != b.x ? a.x < b.x : a.y < b.y; });
p.erase(unique(p.begin(), p.end()), p.end());
int n = p.size();
if (n <= 2) return p;
vector<Point> lo, up;
for (Point q : p) { // нижняя огибающая
while (lo.size() >= 2 && (lo[lo.size()-1] - lo[lo.size()-2]) % (q - lo[lo.size()-1]) <= 0) lo.pop_back();
lo.push_back(q);
}
for (int i = n - 1; i >= 0; --i) { // верхняя огибающая
Point q = p[i];
while (up.size() >= 2 && (up[up.size()-1] - up[up.size()-2]) % (q - up[up.size()-1]) <= 0) up.pop_back();
up.push_back(q);
}
lo.pop_back(); up.pop_back(); // общие концы
lo.insert(lo.end(), up.begin(), up.end());
return lo; // против часовой стрелки, без коллинеарных
}166:21 Дано $n$ точек; найти три, образующие треугольник наибольшей площади. Утверждение: все три вершины можно взять на выпуклой оболочке. Действительно, пусть вершина $A$ не на оболочке; рассмотрим противоположную ей сторону $BC$. Проведём через самую удалённую от прямой $BC$ точку (она даёт наибольшую высоту) параллельную $BC$ прямую — самая удалённая точка всегда на оболочке (иначе параллельная прямая рассекала бы оболочку, и нашлась бы точка выше). Значит, вершину можно заменить на точку оболочки без уменьшения площади. Поэтому: строим оболочку $A_0,\dots,A_{m-1}$ и решаем задачу на выпуклом многоугольнике.
171:07 Фиксируем вершину $A_i$. Перебираем $A_j$ ($j>i$) против часовой стрелки; третья вершина $A_k$ — та, что максимально удалена от прямой $A_iA_j$. Высота над прямой по мере движения от $A_j$ сначала растёт, потом убывает (выпуклость), а при росте $j$ оптимальное $k$ только сдвигается вперёд. Поэтому поддерживаем указатель $k$: пока площадь $A_iA_jA_{k+1}$ больше площади $A_iA_jA_k$ — сдвигаем $k$. Время $O(m^2)$.
// h — выпуклая оболочка против часовой стрелки, m = h.size() >= 3
long long best = 0;
for (int i = 0; i < m; ++i) {
int k = (i + 2) % m;
for (int j = (i + 1) % m; j != i; j = (j + 1) % m) {
if (j == k) k = (k + 1) % m;
while (true) {
int nk = (k + 1) % m;
if (nk == i) break;
if (llabs((h[j] - h[i]) % (h[nk] - h[i])) > llabs((h[j] - h[i]) % (h[k] - h[i]))) k = nk;
else break;
}
if (k != i && k != j) best = max(best, llabs((h[j] - h[i]) % (h[k] - h[i]))); // удвоенная площадь
}
}189:42 Даны $n$ точек. В каждом запросе — подмножество из $k$ точек; нужно найти площадь его оболочки за время $O(n)$ на запрос. Наивно оболочка строится за $O(k\log k)$ — слишком долго при $k\sim n$. В алгоритме Грэхема мешает сортировка по углу относительно опорной точки, которая зависит от подмножества. Но в версии Эндрю сортировка идёт по координатам, которые не зависят от подмножества: сортируем все точки один раз заранее и знаем номер каждой точки в глобальном порядке; для подмножества сортируем номера сортировкой подсчётом за $O(n)$ и применяем линейный проход.
190:22 (Можно было сортировать и по углу относительно фиксированной внешней точки, сохраняя порядок, но потребовалось бы два прохода в разных направлениях; сортировка по координате проще.)
195:47 Дан выпуклый многоугольник и прямая $\ell$. Две касательные, параллельные $\ell$, касаются многоугольника в точках с минимальной и максимальной «высотой» (со знаком) над $\ell$. Находим их так: стороны многоугольника как векторы, нарисованные из начала, идут в порядке углов (это обход против часовой стрелки; начинаем с самой нижней вершины, тогда сортировать не нужно). Направляющий вектор прямой $\vec v=(-B,A)$ и вектор $-\vec v$ попадают в промежутки между векторами сторон, выходящих и входящих в точки касания. Значит, номер точки касания — результат lower_bound по углу (с компаратором из полуплоскостей, как при сортировке по углу) по массиву векторов сторон: $O(\log n)$.
200:34 Следствие: ширину проекции многоугольника на прямую (запрос: «какова длина проекции») находим по двум точкам касания перпендикулярных к ней прямых.
204:39 Опорная точка — самая нижняя левая вершина $A_0$. Остальные вершины идут по возрастанию угла относительно неё. Для запроса $Q$: если $Q$ ниже или вне «веера» — снаружи; иначе бинарным поиском находим сектор между $A_0A_i$ и $A_0A_{i+1}$, куда попадает $Q$, и проверяем принадлежность треугольнику $A_0A_iA_{i+1}$ — только по стороне $A_iA_{i+1}$.
// h[0] — опорная вершина, h против часовой стрелки, n >= 3
bool inConvex(const vector<Point> &h, Point q) {
int n = h.size();
Point v = q - h[0];
if ((h[1] - h[0]) % v < 0 || (h[n-1] - h[0]) % v > 0) return false; // вне веера
int lo = 1, hi = n - 1;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if ((h[mid] - h[0]) % v >= 0) lo = mid; else hi = mid;
}
return (h[lo + 1] - h[lo]) % (q - h[lo]) >= 0; // с границей
}207:27 Задача: выпуклая оболочка множества и добавляемая точка $P$, спрашивают площадь новой оболочки. Если $P$ внутри или на границе — площадь прежняя. Если снаружи, то новая оболочка получается проведением двух касательных из $P$: между точками касания старая «видимая» часть границы заменяется двумя новыми сторонами. Площадь находится по префиксным суммам векторных произведений $A_i\times A_{i+1}$ на отрезке границы плюс вклад двух новых сторон. Остаётся быстро находить точки касания.
214:20 Сопоставим каждой вершине «угол» $\varphi_i$ — угол вектора $\vec{PA_i}$ относительно любой прямой через $P$, оставляющей многоугольник по одну сторону. Касательные — это точки минимума и максимума $\varphi$. Функция $\varphi$ по циклу битоническая: между минимумом и максимумом она растёт (против часовой), от максимума к минимуму убывает. Если у соседних вершин углы равны, касательная идёт по стороне — минимум не единственный, берём любую из таких вершин.
218:26 Пусть $K$ — наибольшее с $2^K\le n$. Начинаем с произвольного индекса $i$ и идём по степеням двойки от $K$ до $0$: на шаге с $s=2^k$ рассматриваем три индекса $i$, $i+s$, $i-s$ (по модулю $n$) и заменяем $i$ на тот из них, где функция минимальна.
int K = 0;
while ((1 << (K + 1)) <= n) K++;
int i = 0;
for (int k = K; k >= 0; --k) {
int cand[3] = {i, (i + (1 << k)) % n, ((i - (1 << k)) % n + n) % n};
int best = cand[0];
for (int c = 1; c < 3; ++c)
if (less(cand[c], best)) best = cand[c]; // less: сравнение значений функции
i = best;
}
// i — индекс минимума223:12 Для нахождения максимума берём в тройке индекс с максимальным значением. Значения функции не нужны — нужен только компаратор: чтобы сравнить $\varphi_i$ и $\varphi_j$ достаточно знака векторного произведения $\vec{PA_i}\times\vec{PA_j}$ ($>0$ означает, что $\varphi_i<\varphi_j$). Здесь прямая отсчёта не нужна, так как все вершины видны из $P$ под углом меньше $180^\circ$.
229:29 Считаем значения функции различными (равенства разбираются по индексу). Назовём $\mathrm{top}$-$m$ множество $m$ вершин с наименьшими значениями. Так как функция битоническая, $\mathrm{top}$-$m$ — это дуга из $m$ подряд идущих индексов, содержащая минимум, и дуги вложены. Утверждение: после итерации с $s=2^k$ текущий индекс $i$ лежит в $\mathrm{top}$-$2^k$. Тогда после последней итерации ($k=0$) он в $\mathrm{top}$-$1$, то есть является минимумом.
233:13 Индукция по убыванию $k$. До первой итерации $i$ лежит в $\mathrm{top}$-$2^{K+1}$ (так как $2^{K+1}>n$, туда входят все вершины). Переход: пусть $i\in\mathrm{top}$-$2^{k+1}$. Эта дуга длины $2^{k+1}$ шире дуги $\mathrm{top}$-$2^k$ суммарно на $2^k$ позиций (слева и справа). Если $i$ уже в $\mathrm{top}$-$2^k$, то минимальный из трёх кандидатов имеет значение не больше $f(i)$ и потому тоже в $\mathrm{top}$-$2^k$. Если $i$ в левой добавке на расстоянии $j\le 2^k$ от дуги, то кандидат $i+2^k$ оказывается внутри дуги $\mathrm{top}$-$2^k$ (на расстоянии $2^k-j<2^k$ от её начала); для правой добавки симметрично кандидат $i-2^k$. Значит, среди кандидатов есть элемент $\mathrm{top}$-$2^k$, и выбор минимума остаётся в этой дуге.
241:15 Эта часть — запись разбора, выложенная отдельно после занятия. Задача: массив с онлайн-запросами «вставить число в позицию» и «количество различных на $[l,r]$». Решение — корневая декомпозиция по запросам: каждые $K$ запросов массив $A$ перестраиваем и храним «дельту» — до $K$ добавленных элементов с позициями вставки (между $a_i$ и $a_{i+1}$ статического массива).
245:20 Запрос $[l,r]$ превращается в подотрезок $[l',r']$ статического массива плюс несколько вставленных элементов. Поправка за вставленные: для каждого различного вставленного значения прибавляем $1$, если оно не встречается на $[l',r']$. Чтобы не делать бинпоиск, при вставке запоминаем ближайшие вхождения этого значения слева и справа (за $O(\log n)$ один раз) и проверяем попадание в $[l',r']$ за $O(1)$.
249:25 Остаётся статический массив с онлайн-запросами «число различных на подотрезке», строить за $O(n)$, отвечать за $O(\sqrt n)$. Разбиваем массив на блоки размера $\sqrt n$. Для каждого элемента считаем $L_i$ — предыдущее вхождение того же значения; элемент даёт $1$ к ответу на $[l,r]$, если $L_i<l$. Хвосты, не совпадающие с границами блоков, обрабатываем поэлементно за $O(\sqrt n)$. Для границ блоков строим таблицу $c_{i,j}$ — число элементов блока $j$ с $L$ левее границы блока $i$: по каждой паре блоков (сначала накопить количество «ровно в блок $i$», потом префиксные суммы по строке). Матрица $\sqrt n\times\sqrt n$ строится за $O(n)$, запрос — сумма $\sqrt n$ ячеек.
257:35 В записи — краткий разбор задач контеста; ниже по одной идее на задачу (формулировки пересказаны сжато, а некоторые задачи лектором были названы «были на лекции» и пропущены).
set свободных номеров и lower_bound. Урок: иногда set вместо дерева отрезков.set позиции, где $s_j\ne9$; число изменившихся цифр — расстояние до первой «не девятки» справа, а наличие переноса — по первой «не девятке» слева ($<9$ — переноса нет, $>9$ — есть).