e-maxx_algo

for (int i=0; i<n; ++i) if (!used[i])

dfs1 (i);

comp.assign (n, -1);

for (int i=0, j=0; i<n; ++i) { int v = order[n-i-1]; if (comp[v] == -1)

dfs2 (v, j++);

}

for (int i=0; i<n; ++i)

if (comp[i] == comp[i^1]) { puts ("NO SOLUTION"); return 0;

}

for (int i=0; i<n; ++i) {

int ans = comp[i] > comp[i^1] ? i : i^1; printf ("%d ", ans);

}

}

Список задач, которые можно решить, используя heavy-light декомпозицию:

Длина объединения отрезков на прямой за O (N log N)

Даны N отрезков на прямой, т.е. каждый отрезок задаётся парой координат (X1, X2). Рассмотрим объединение этих отрезков и найдём его длину.

Алгоритм был предложен Кли (Klee) в 1977 году. Алгоритм работает за O (N log N). Было доказано, что этот алгоритм является быстрейшим (асимптотически).

Описание

Положим все координаты концов отрезков в массив X и отсортируем его по значению координаты.

Дополнительное условие при сортировке - при равенстве координат первыми должны идти левые концы. Кроме того, для каждого элемента массива будем хранить, относится он к левому или к правому концу отрезка. Теперь пройдёмся по всему массиву, имея счётчик C перекрывающихся отрезков. Если C отлично от нуля, то к результату добавляем разницу Xi - Xi-1. Если текущий элемент относится к левому концу, то увеличиваем счётчик C, иначе уменьшаем его.

Реализация

unsigned segments_union_measure (const vector <pair <int,int> > & a)

{

unsigned n = a.size();

vector <pair <int,bool> > x (n*2); for (unsigned i=0; i<n; i++)

{

x[i*2] = make_pair (a[i].first, false); x[i*2+1] = make_pair (a[i].second, true);

}

sort (x.begin(), x.end());

unsigned result = 0; unsigned c = 0;

for (unsigned i=0; i<n*2; i++)

{

if (c && i)

result += unsigned (x[i].first - x[i-1].first); if (x[i].second)

++c;

else

--c;

}

return result;

}

Знаковая площадь треугольника и предикат "По часовой стрелке"

Определение

Пусть даны три точки , , . Найдём значение знаковой площади треугольника , т.е. площади этого треугольника, взятой со знаком плюс или минус в зависимости от типа поворота, образуемого точками , , : против часовой стрелки или по ней соответственно.

Понятно, что, если мы научимся вычислять такую знаковую ("ориентированную") площадь, то сможем и находить обычную площадь любого треугольника, а также сможем проверять, по часовой стрелке или против направлена какаялибо тройка точек.

Вычисление

Воспользуемся понятием косого (псевдоскалярного) произведения векторов. Оно как раз равно удвоенной знаковой площади треугольника:

где угол берётся ориентированным, т.е. это угол вращения между этими векторами против часовой стрелки. (Модуль косого произведения двух векторов равен модулю векторного произведения их.)

Косое произведение вычисляется как величина определителя, составленного из координат точек:

Раскрывая определитель, можно получить такую формулу:

Можно сгруппировать третье слагаемое с первыми двумя, избавившись от одного умножения:

Последнюю формулу удобно записывать и запоминать в матричном виде, как следующий определитель:

Реализация

Функция, вычисляющая удвоенную знаковую площадь треугольника:

int triangle_area_2 (int x1, int y1, int x2, int y2, int x3, int y3) { return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);

}

Функция, возвращающая обычную площадь треугольника:

double triangle_area (int x1, int y1, int x2, int y2, int x3, int y3) { return abs (triangle_area_2 (x1, y1, x2, y2, x3, y3)) / 2.0;

}

Функция, проверяющая, образует ли указанная тройка точек поворот по часовой стрелке:

bool clockwise (int x1, int y1, int x2, int y2, int x3, int y3) { return triangle_area_2 (x1, y1, x2, y2, x3, y3) < 0;

}

Функция, проверяющая, образует ли указанная тройка точек поворот против часовой стрелки:

bool counter_clockwise (int x1, int y1, int x2, int y2, int x3, int y3) { return triangle_area_2 (x1, y1, x2, y2, x3, y3) > 0;

}

Проверка двух отрезков на пересечение

Даны два отрезка и (они могут вырождаться в точки). Требуется проверить, пересекаются они или нет. Если дополнительно требуется найти саму точку (точки) пересечения, то см. соответствующую статью.

Первый способ: ориентированная площадь треугольника

Воспользуемся Ориентированной площадью треугольника и предикат 'По часовой стрелке'. Действительно, чтобы

вычисляя ориентированные площади соответствующих треугольников и сравнивая их знаки.

Единственное, на что следует обратить внимание — граничные случаи, когда какие-то точки попадают на саму прямую. При этом возникает единственный особый случай, когда вышеописанные проверки ничего не дадут — случай, когда оба отрезка лежат на одной прямой. Этот случай надо рассмотреть отдельно. Для этого достаточно проверить, что проекции этих двух отрезков на оси и пересекаются (часто эту проверку называют "проверкой на bounding box").

В целом, этот способ — более простой, чем тот, что будет приведён ниже (производящий пересечение двух прямых), и имеет меньше особых случаев, однако главный его недостаток — в том, что он не находит саму точку пересечения.

Реализация:

struct pt {

int x, y;

};

inline int area (pt a, pt b, pt c) {

return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

}

inline bool intersect_1 (int a, int b, int c, int d) { if (a > b) swap (a, b);

if (c > d) swap (c, d); return max(a,c) <= min(b,d);

}

bool intersect (pt a, pt b, pt c, pt d) { return intersect_1 (a.x, b.x, c.x, d.x)

&&intersect_1 (a.y, b.y, c.y, d.y)

&&area(a,b,c) * area(a,b,d) <= 0

&&area(c,d,a) * area(c,d,b) <= 0;

}

В целях оптимизации проверка на bounding box вынесена в начало, до вычисления площадей — поскольку это более "лёгкая" проверка.

Второй способ: пересечение двух прямых

Вместо пересечения отрезков выполним пересечение двух прямых, в результате, если прямые не параллельны,

получим какую-то точку, которую надо проверить на принадлежность обоим отрезкам; для этого достаточно проверить, что эта точка принадлежит обоим отрезкам в проекции на ось и на ось .

Если же прямые оказались параллельными, то, если они не совпадают, то отрезки точно не пересекаются. Если же прямые совпали, то отрезки лежат на одной прямой, и для проверки их пересечения достаточно проверить, что пересекаются их проекции на ось и .

Остаётся ещё особый случай, когда один или оба отрезка вырождаются в точки: в таком случае говорить о прямых некорректно, и этот метод будет неприменим (этот случай надо будет разбирать отдельно).

Реализация (без учёта случая вырожденных отрезков):

struct pt {

int x, y;

};

const double EPS = 1E-9;

inline int det (int a, int b, int c, int d) { return a * d - b * c;

}

inline bool between (int a, int b, double c) {

return min(a,b) <= c + EPS && c <= max(a,b) + EPS;

}

inline bool intersect_1 (int a, int b, int c, int d) { if (a > b) swap (a, b);

if (c > d) swap (c, d); return max(a,c) <= min(b,d);

}

bool intersect (pt a, pt b, pt c, pt d) {

int A1 = a.y-b.y, B1 = b.x-a.x, C1 = -A1*a.x - B1*a.y; int A2 = c.y-d.y, B2 = d.x-c.x, C2 = -A2*c.x - B2*c.y; int zn = det (A1, B1, A2, B2);

if (zn != 0) {

double x = - det (C1, B1, C2, B2) * 1. / zn; double y = - det (A1, C1, A2, C2) * 1. / zn;

return between (a.x, b.x, x) && between (a.y, b.y, y)

&& between (c.x, d.x, x) && between (c.y, d.y, y);

}

else

return det (A1, C1, A2, C2) == 0 && det (B1, C1, B2, C2) == 0

&&intersect_1 (a.x, b.x, c.x, d.x)

&&intersect_1 (a.y, b.y, c.y, d.y);

}

Здесь сначала вычисляется коэффициент — знаменатель в формуле Крамера. Если , то коэффициенты и прямых пропорциональны, и прямые параллельны или совпадают. В этом случае надо проверить, совпадают они или нет, для чего надо проверить, что коэффициенты прямых пропорциональны с тем же коэффициентом, для чего достаточно вычислить два следующих определителя, если они оба равны нулю, то прямые совпадают:

Следует отметить, что если исходные координаты точек уже были вещественнозначными, то следует нормировать прямые (т.е. привести их к такому состоянию, что сумма квадратов коэффициентов и равна единице), иначе погрешности при сравнении прямых на параллельность и на совпадение могут оказаться слишком большими.

Нахождение уравнения прямой для отрезка

Задача — по заданным координатам конца отрезка построить прямую, проходящую через него.

Мы считаем, что отрезок невырожден, т.е. имеет длину больше нуля (иначе, понятно, через него проходит бесконечно много различных прямых).

Двумерный случай

Пусть дан отрезок , т.е. известны координаты его концов , , , .

Требуется построить уравнение прямой на плоскости, проходящей через этот отрезок, т.е. найти коэффициенты , , в уравнении прямой:

Заметим, что искомых троек , проходящих через заданный отрезок, бесконечно много:

можно умножить все три коэффициента на произвольное ненулевое число и получить ту же самую прямую. Следовательно, наша задача — найти одну из таких троек.

Нетрудно убедиться (подстановкой этих выражений и координат точек и в уравнение прямой), что подходит следующий набор коэффициентов:

Целочисленный случай

Важным преимуществом такого способа построения прямой является то, что если координаты концов были целочисленными, то и полученные коэффициенты также будут целочисленными. В некоторых случаях это позволяет производить геометрические операции, вообще не прибегая к вещественным числам.

Однако есть и небольшой недостаток: для одной и той же прямой могут получаться разные тройки коэффициентов. Чтобы избежать этого, но не уходить от целочисленных коэффициентов, можно применить следующий приём,

все три коэффициента на . В итоге мы придём к тому, что для одинаковых прямых будут получаться одинаковые тройки коэффициентов, что позволит легко проверять прямые на равенство.

Вещественнозначный случай

При работе с вещественными числами следует всегда помнить о погрешностях.

Коэффициенты и получаются у нас порядка исходных координат, коэффициент — уже порядка квадрата от них. Это уже может быть достаточно большими числами, а, например, при пересечении прямых они станут ещё

больше, что может привести к большим ошибкам округления уже при исходных координатах порядка .

Поэтому при работе с вещественными числами желательно производить так называемую нормировку прямой: а именно, делать коэффициенты такими, чтобы . Для этого надо вычислить число :

и разделить все три коэффициента , , на него.

Тем самым, порядок коэффициентов и уже не будет зависеть от порядка входных координат, а коэффициент будет того же порядка, что и входные координаты. На практике это приводит к значительному улучшению

точности вычислений.

Наконец, упомянем о сравнении прямых — ведь после такой нормировки для одной и той же прямой