e-maxx_algo
.pdfРешение этой системы сводится к решению квадратного уравнения. Мы опустим все громоздкие выкладки, и сразу приведём готовый ответ:
Итого у нас получилось решений вместо . Однако легко понять, в каком месте возникают лишние решения: на самом деле, в последней системе достаточно брать только одно решение (например, первое). В самом деле, геометрический смысл того, что мы берём и , понятен: мы фактически перебираем, по какую сторону
от каждой из окружностей будет прямая. Поэтому два способа, возникающие при решении последней системы, избыточны: достаточно выбрать одно из двух решений (только, конечно, во всех четырёх случаях надо выбрать одно и то же семейство решений).
Последнее, что мы ещё не рассмотрели — это как сдвигать прямые в том случае, когда первая окружность не находилась изначально в начале координат. Однако здесь всё просто: из линейности уравнения прямой следует, что
от коэффициента надо отнять величину |
(где |
и |
— координаты первоначального центра |
первой окружности). |
|
|
|
Реализация
Опишем сначала все необходимые структуры данных и другие вспомогательные определения:
struct pt {
double x, y;
pt operator- (pt p) {
pt res = { x-p.x, y-p.y }; return res;
}
};
struct circle : pt { double r;
};
struct line {
double a, b, c;
};
const double EPS = 1E-9;
double sqr (double a) { return a * a;
}
Тогда само решение можно записать таким образом (где основная функция для вызова — вторая; а первая функция
— вспомогательная):
void tangents (pt c, double r1, double r2, vector<line> & ans) { double r = r2 - r1;
double z = sqr(c.x) + sqr(c.y); double d = z - sqr(r);
if (d < -EPS) return; d = sqrt (abs (d)); line l;
l.a = (c.x * r + c.y * d) / z; l.b = (c.y * r - c.x * d) / z; l.c = r1;
ans.push_back (l);
}
vector<line> tangents (circle a, circle b) { vector<line> ans;
for (int i=-1; i<=1; i+=2)
for (int j=-1; j<=1; j+=2)
tangents (b-a, a.r*i, b.r*j, ans); for (size_t i=0; i<ans.size(); ++i)
ans[i].c -= ans[i].a * a.x + ans[i].b * a.y; return ans;
}
Сформулируем ключевые утверждения:
●Для поиска пересекающейся пары достаточно рассматривать при каждом фиксированном положении сканирующей прямой только соседние отрезки.
● Достаточно рассматривать сканирующую прямую не во всех возможных действительных позициях |
, |
а только в тех позициях, когда появляются новые отрезки или исчезают |
|
старые. Иными словами, достаточно ограничиться лишь только положениями, равными абсциссам точек- |
|
концов отрезков. |
|
●При появлении нового отрезка достаточно вставить его в нужное место в список, полученный для предыдущей сканирующей прямой. Проверять на пересечение надо только добавляемый отрезок с его непосредственными соседями в списке сверху и снизу.
●При исчезновении отрезка достаточно удалить его из текущего списка. После этого надо проверить на пересечение с верхним и нижним соседями в списке.
●Других изменений в порядке следования отрезков в списке, кроме описанных, не существует. Других проверок на пересечения производить не надо.
Для понимания истинности этих утверждений достаточно следующих замечаний:
●Два непересекающихся отрезка никогда не меняют своего относительного порядка.
Всамом деле, если один отрезок сначала был выше другого, а затем стал ниже, то между двумя этими моментами произошло пересечение этих двух отрезков.
●Иметь совпадающие -координаты два непересекающихся отрезка также не могут.
●Из этого следует, что в момент появления отрезка мы можем найти в очереди позицию для этого отрезка, и больше этот отрезок переставлять в очереди не придётся: его порядок относительно других отрезков в очереди меняться не будет.
●Два пересекающихся отрезка в момент точки своего пересечения окажутся соседями друг друга в очереди.
●Следовательно, для нахождения пары пересекающихся отрезков достаточно проверить на пересечение только все те пары отрезков, которые когда-нибудь за время движения сканирующей прямой хотя бы раз были соседями друг друга.
Легко заметить, что этого достаточно лишь проверять добавляемый отрезок со своими верхним и нижним соседями, а также при удалении отрезка — его верхнего и нижнего соседей (которые после удаления станут соседями друг друга).
●Следует обратить внимание, что при фиксированном положении сканирующей прямой мы сначала должны произвести добавление всех появляющихся здесь отрезков, и лишь затем — удаление всех исчезающих здесь отрезков.
Тем самым, мы не пропустим пересечения отрезков по вершине: т.е. такие случаи, когда два отрезка имеют общую вершину.
●Заметим, что вертикальные отрезки на самом деле никак не влияют на корректность алгоритма.
Эти отрезки выделяются тем, что они появляются и исчезают в один и тот же момент времени. Однако, за счёт предыдущего замечания, мы знаем, что сначала все отрезки будут добавлены в очередь, и лишь затем будут удалены. Следовательно, если вертикальный отрезок пересекается с каким-то другим открытым в этот момент отрезком (в том числе вертикальным), то это будет обнаружено.
Вкакое место очереди помещать вертикальные отрезки? Ведь вертикальный отрезок не имеет одной определённой
-координаты, он простирается на целый отрезок по -координате. Однако легко понять, что в качестве - координаты можно взять любую координату из этого отрезка.
Таким образом, весь алгоритм совершит не более |
тестов на пересечение пары отрезков, и совершит |
операций с очередью отрезков (по операций в моменты появления и исчезновения каждого отрезка). Итоговая асимптотика алгоритма составляет, таким образом, .
Реализация
Приведём полную реализацию описанного алгоритма:
const double EPS = 1E-9;
struct pt {
double x, y;
};
struct seg {
pt p, q; int id;
double get_y (double x) const {
if (abs (p.x - q.x) < EPS) return p.y;
return p.y + (q.y - p.y) * (x - p.x) / (q.x - p.x);
}
};
inline bool intersect1d (double l1, double r1, double l2, double r2) { if (l1 > r1) swap (l1, r1);
if (l2 > r2) swap (l2, r2);
return max (l1, l2) <= min (r1, r2) + EPS;
}
inline int vec (const pt & a, const pt & b, const pt & c) {
double s = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); return abs(s)<EPS ? 0 : s>0 ? +1 : -1;
}
bool intersect (const seg & a, const seg & b) {
return intersect1d (a.p.x, a.q.x, b.p.x, b.q.x)
&&intersect1d (a.p.y, a.q.y, b.p.y, b.q.y)
&&vec (a.p, a.q, b.p) * vec (a.p, a.q, b.q) <= 0
&&vec (b.p, b.q, a.p) * vec (b.p, b.q, a.q) <= 0;
}
bool operator< (const seg & a, const seg & b) {
double x = max (min (a.p.x, a.q.x), min (b.p.x, b.q.x)); return a.get_y(x) < b.get_y(x) - EPS;
}
struct event { double x; int tp, id;
event() { }
event (double x, int tp, int id) : x(x), tp(tp), id(id)
{ }
bool operator< (const event & e) const {
if (abs (x - e.x) > EPS) return x < e.x; return tp > e.tp;
}
};
set<seg> s;
vector < set<seg>::iterator > where;
inline set<seg>::iterator prev (set<seg>::iterator it) { return it == s.begin() ? s.end() : --it;
}
inline set<seg>::iterator next (set<seg>::iterator it) { return ++it;
}
pair<int,int> solve (const vector<seg> & a) { int n = (int) a.size();
vector<event> e;
for (int i=0; i<n; ++i) {
e.push_back (event (min (a[i].p.x, a[i].q.x), +1, i)); e.push_back (event (max (a[i].p.x, a[i].q.x), -1, i));
}
sort (e.begin(), e.end());
s.clear();
where.resize (a.size());
for (size_t i=0; i<e.size(); ++i) { int id = e[i].id;
if (e[i].tp == +1) { set<seg>::iterator
nxt = s.lower_bound (a[id]), prv = prev (nxt);
if (nxt != s.end() && intersect (*nxt, a[id])) return make_pair (nxt->id, id);
if (prv != s.end() && intersect (*prv, a[id])) return make_pair (prv->id, id);
where[id] = s.insert (nxt, a[id]);
}
else {
set<seg>::iterator
nxt = next (where[id]), prv = prev (where[id]);
if (nxt != s.end() && prv != s.end() &&
intersect (*nxt, *prv))
return make_pair (prv->id, nxt->id); s.erase (where[id]);
}
}
return make_pair (-1, -1);
}
Основная функция здесь — |
, которая возвращает номера найденных пересекающихся отрезков, |
|
|||
либо |
, если пересечения отсутствуют. |
|
|
||
Проверка на пересечение двух отрезков осуществляется функцией |
, с помощью алгоритма на |
|
|||
основе ориентированной площади треугольника. |
|
|
|||
Очередь отрезков в глобальной переменной |
— |
. Итераторы, указывающие положение |
. |
||
каждого отрезка в очереди (для удобного удаления отрезков из очереди), хранятся в глобальном массиве |
|||||
Введены также две вспомогательные функции |
и |
, которые возвращают итераторы на предыдущий |
|||
и следующий элементы (либо |
, если такового не существует). |
|
|||
Константа |
обозначает погрешность сравнения двух вещественных чисел (в основном она используется |
|
при проверке двух отрезков на пересечение).
Z-функция строки и её вычисление
Пусть дана строка длины . Тогда Z-функция ("зет-функция") от этой строки — это массив длины , -ый
элемент которого равен наибольшему числу символов, начиная с позиции , совпадающих с первыми символами строки . Иными словами, — это наибольший общий префикс строки и её -го суффикса.
Примечание. В данной статье, во избежание неопределённости, мы будем считать строку 0-индексированной — т. е. первый символ строки имеет индекс , а последний — .
Первый элемент Z-функции, , обычно считают неопределённым. В данной статье мы будем считать, что он равен нулю (хотя ни в алгоритме, ни в приведённой реализации это ничего не меняет).
В данной статье приводится алгоритм вычисления Z-функции за время |
, а также различные применения |
этого алгоритма. |
|
Примеры
Приведём для примера подсчитанную Z-функцию для нескольких строк:
●:
●:
●:
Тривиальный алгоритм
Формальное определение можно представить в виде следующей элементарной реализации за :
vector<int> z_function_trivial (string s) { int n = (int) s.length(); vector<int> z (n);
for (int i=1; i<n; ++i)
while (i + z[i] < n && s[z[i]] == s[i+z[i]]) ++z[i];
return z;
}
Мы просто для каждой позиции перебираем ответ для неё , начиная с нуля, и до тех пор, пока мы не
обнаружим несовпадение или не дойдём до конца строки.
Разумеется, эта реализация слишком неэффективна, перейдём теперь к построению эффективного алгоритма.
Эффективный алгоритм вычисления Z-функции
Чтобы получить эффективный алгоритм, будем вычислять значения |
по очереди — от |
до |
, и при |
этом постараемся при вычислении очередного значения максимально использовать уже вычисленные значения.
Назовём для краткости подстроку, совпадающую с префиксом строки , отрезком совпадения. Например, значение искомой Z-функции — это длиннейший отрезок совпадения, начинающийся в позиции
(и заканчиваться он будет в позиции ).
Для этого будем поддерживать координаты |
самого правого отрезка совпадения, т.е. из |
всех обнаруженных отрезков будем хранить тот, который оканчивается правее всего. В некотором смысле, индекс — это такая граница, до которой наша строка уже была просканирована алгоритмом, а всё остальное — пока ещё не известно.
Тогда если текущий индекс, для которого мы хотим посчитать очередное значение Z-функции, — это , мы имеем один из двух вариантов:
● — т.е. текущая позиция лежит за пределами того, что мы уже успели обработать.
Тогда будем искать |
тривиальным алгоритмом, т.е. просто пробуя значения |
, |
, и т. |
||
д. Заметим, что в итоге, если |
окажется |
, то мы будем обязаны обновить координаты самого правого |
|
отрезка — т.к. гарантированно окажется больше .
● — т.е. текущая позиция лежит внутри отрезка совпадения .
Тогда мы можем использовать уже подсчитанные предыдущие значения Z-функции, чтобы проинициализировать значение не нулём, а каким-то возможно бОльшим числом.
Для этого заметим, что подстроки |
и |
совпадают. Это означает, что в качестве |
||
начального приближения для |
можно взять соответствующее ему значение из отрезка |
, а |
||
именно, значение |
. |
|
|
|
Однако значение |
могло оказаться слишком большим: таким, что при применении его к позиции |
оно |
"вылезет" за пределы границы . Этого допустить нельзя, т.к. про символы правее мы ничего не знаем, и они могут отличаться от требуемых.
Приведём пример такой ситуации, на примере строки:
|
|
|
|
Когда мы дойдём до последней позиции ( |
), текущим самым правым отрезком будет |
. Позиции с |
|
учётом этого отрезка будет соответствовать позиция |
, ответ в которой равен |
. Очевидно, что |
|
таким значением инициализировать |
нельзя, оно совершенно некорректно. Максимум, каким значением мы |
могли проинициализировать — это , поскольку это наибольшее значение, которое не вылазит за пределы отрезка . Таким образом, в качестве начального приближения для безопасно брать только такое выражение:
|
|
|
Проинициализировав |
таким значением |
, мы снова дальше действуем тривиальным алгоритмом |
— потому что после границы , вообще говоря, могло обнаружиться продолжение отрезка совпадение, предугадать которое одними лишь предыдущими значениями Z-функции мы не могли.
Таким образом, весь алгоритм представляет из себя два случая, которые фактически различаются только начальным значением : в первом случае оно полагается равным нулю, а во втором
— определяется по предыдущим значениям по указанной формуле. После этого обе ветки алгоритма сводятся к выполнению тривиального алгоритма, стартующего сразу с указанного начального значения.
Алгоритм получился весьма простым. Несмотря на то, что при каждом в нём так или иначе выполняется тривиальный алгоритм — мы достигли существенного прогресса, получив алгоритм, работающий за линейное время. Почему это так, рассмотрим ниже, после того, как приведём реализацию алгоритма.
Реализация
Реализация получается весьма лаконичной:
vector<int> z_function (string s) {
Таким образом, мы доказали, что каждая итерация вложенного цикла приводит к продвижению указателя вправо. Т.к.
не могло оказаться больше , это означает, что всего этот цикл сделает не более итерации.
Поскольку вся остальная часть алгоритма, очевидно, работает за |
, то мы доказали, что и весь алгоритм |
вычисления Z-функции выполняется за линейное время. |
|
Применения
Рассмотрим несколько применений Z-функции при решении конкретных задач. Применения эти будут во многом аналогичным применениям префикс-функции.
Поиск подстроки в строке
Во избежании путаницы, назовём одну строку текстом , другую — образцом . Таким образом, задача заключается в том, чтобы найти все вхождения образца в текст .
Для решения этой задачи образуем строку |
, т.е. к образцу припишем текст через символ- |
разделитель (который не встречается нигде в самих строках).
Посчитаем для полученной строки Z-функцию. Тогда для любого в отрезке |
по |
|
соответствующему значению |
можно понять, входит ли образец |
в текст , начиная с |
позиции : если это значение Z-функции равно |
, то да, входит, иначе — нет. |
|
Таким образом, асимптотика решения получилась |
. Потребление памяти имеет ту |
|
же асимптотику. |
|
|
Количество различных подстрок в строке
Дана строка длины . Требуется посчитать количество её различных подстрок.
Будем решать эту задачу итеративно. А именно, научимся, зная текущее количество различных подстрок, пересчитывать это количество при добавлении в конец одного символа.
Итак, пусть — текущее количество различных подстрок строки , и мы добавляем в конец символ . Очевидно, в результате могли появиться некоторые новые подстроки, оканчивавшиеся на этом новом символе (а именно, все подстроки, оканчивающиеся на этом символе, но не встречавшиеся раньше).
Возьмём строку и инвертируем её (запишем символы в обратном порядке). Наша задача — посчитать, сколько у строки таких префиксов, которые не встречаются в ней более нигде. Но если мы посчитаем
для строки Z-функцию и найдём её максимальное значение |
, то, очевидно, в строке встречается (не в начале) |
|||
её префикс длины |
, но не большей длины. Понятно, префиксы меньшей длины уже точно встречаются в ней. |
|||
Итак, мы получили, что число новых подстрок, появляющихся при дописывании символа , равно |
, где |
|||
— текущая длина строки после приписывания символа . |
|
|
|
|
Следовательно, асимптотика решения для строки длины составляет |
. |
|
||
Стоит заметить, что совершенно аналогично можно пересчитывать за |
количество различных подстрок и |
|
при дописывании символа в начало, а также при удалении символа с конца или с начала.
Сжатие строки
Дана строка длины . Требуется найти самое короткое её "сжатое" представление, т.е. найти такую строку наименьшей длины, что можно представить в виде конкатенации одной или нескольких копий .
Для решения посчитаем Z-функцию строки , и найдём первую позицию такую, что |
, и при этом |
делится на . Тогда строку можно сжать до строки длины . |
|
Доказательство такого решения практически не отличается от доказательства решения с помощью префикс-функции.
Задачи в online judges
Список задач, которые можно решить, используя Z-функцию:
● UVA #455 "Periodic Strings" [сложность: средняя]
● UVA #11022 "String Factoring" [сложность: средняя]