Настройки поиска (Страница 3 из 9)

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

Отсортируем все икс координаты по возрастанию и сделаем заметание вертикальной прямой. Заведем дерево отрезков по игрек координатам, которые встречались среди игрек координат прямоугольников. Когда мы встречаем левую границу прямоугольника, увеличиваем в дереве отрезков значения на отрезке от нижнего до верхнего игрека на 1. Когда встречаем правую границу - уменьшаем значения. После каждой такой операции смотрим максимум в дереве. Тогда максимум среди всех таких максимумов и будет искомой точкой. Сложность O(NlogN).

Во-первых, O(N^2*M) это лишь порядок количества операций, т.е. там N^2*M*C, где C может быть <1.
Во-вторых, столько операций выполняется в худшем случае, в среднем же алгоритм работает быстро.
Вот ссылка на статью, где описан худший случай для алгоритма Диница: http://deepblue.lib.umich.edu/bitstream … 000617.pdf.

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

Да, я после проверки очередной длины очищаю хешсет.

Ради интереса только что сдал с лонг лонговским хешом и ручным хешсетом.

Можно решать, например, так (описано в самом низу страницы).

Можно избавиться от cin/cout, если и так не пройдет - заменить map на отсортированный массив или хешмап.

Нет, в массиве g хранятся не 0 или 1, а списки смежных вершин. То есть g[v] это список всех вершин, которые смежные с v.

http://e-maxx.ru/algo/linear_systems_gauss

В плане - сумма длин это будет сумма ребер цикла. Я когда писал, забыл о максимальном ребре . Для его нахождения нужно просто найти максимум из всех ребер от А до LCA и от B до LCA.

Чтобы сложность вышла линейной, можно после нахождения LCA, запустить дфс и для каждой вершины A в нем перебрать все ребра инцидентные ей, которые не вошли в миностов, для каждого второго конца B взять уже найденный LCA и затем посчитать максимум среди всех ребер от вершины до LCA. Так как мы находимся в дфсе, список вершин, в которых мы побывали но еще не вышли из рекурсии образует путь, причем LCA и A лежат в этом пути, а A является последней вершиной в нем. Можно в стеке хранить возрастающую последовательность номеров ребер и при спуске в рекурсию (добавлению нового ребра) удалять ребра из вершины стека до тех пор, пока они не превышают данное. Затем, максимум от LCA до A сводится к поиску номера i в стеке, такого что i-е ребро лежит ниже на пути чем LCA, а i-1 -е ребро уже выше. Очевидно, что это ребро и будет искомым максимумом. Можно, конечно, это искать бинпоиском, но так как за NlogN можно и проще сделать, я расскажу как это делать за O(1) в среднем.

Когда ребро выпихивается другим ребром из стека, сохраним для него ссылку на то ребро, которое его выпихнуло. Затем, когда выпихнется и то ребро - мы должны изменить ссылку. Это можно делать системой непересекающихся множеств.

Теперь мы научились извлекать максимум и спускаться ниже в рекурсию. Остается вопрос - что делать, когда нам нужно подниматься? При спуске мы сделали О(К) изменений памяти, значит, мы за О(К) можем их всех откатить, вернув в стек ребра и изменив состояние системы непересекающихся множеств. Таким образом, получаем алгоритм, который за О(E) в оффлайне находит все максимумы ребер от A до LCA(A,B), где B - второй конец ребра невошедшего в миностов, инцидентного A.

Если же хочется O(NlogN) - можно просто для каждой вершины предпосчитать максимальное ребро до первой, второй, четвертой и т.д. вершин на пути от данной вершины к корню дерева.

Я не знаю другого алгоритма, но я знаю как этот написать так чтобы он работал быстро. А именно: при добавлении одного ребра мы можем найти LCA двух его концов в MST и посчитать сумму длин путей до LCA. Так как все такие запросы заранее известны, можно второй миностов найти за O(E) при помощи алгоритма Тарьяна при построенном первом миностове.

Для второй задачи это не верно, даже если точки 3. Если треугольник не прямоугольный, то центр описанной окружности не будет лежать на стороне.
Насчет первой - там нужно найти точку пересечения окружностей или кругов? Если окружностей, то там все просто. Для кругов за НлогН скорее всего сканлайном, но пока не понятно как сделать так чтобы не хранить многоугольник с дугами вместо сторон и не обновлять его как-то быстро.