что такое прямая, отрезок

event (double x, int tp, int id)

return a.get_y(x) < b.get_y(x) - EPS;

double x = max (min (a.p.x, a.q.x), min (b.p.x, b.q.x));

bool operator< (const seg & a, const seg & b) {

&& vec (b.p, b.q, a.p) * vec (b.p, b.q, a.q) <= 0;

&& vec (a.p, a.q, b.p) * vec (a.p, a.q, b.q) <= 0

&& intersect1d (a.p.y, a.q.y, b.p.y, b.q.y)

return intersect1d (a.p.x, a.q.x, b.p.x, b.q.x)

bool intersect (const seg & a, const seg & b) {

return abs(s)<EPS ? 0 : s>0 ? +1 : -1;

double s = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

inline int vec (const pt & a, const pt & b, const pt & c) {

return max (l1, l2) <= min (r1, r2) + EPS;

if (l2 > r2) swap (l2, r2);

if (l1 > r1) swap (l1, r1);

inline bool intersect1d (double l1, double r1, double l2, double r2) {

return p.y + (q.y - p.y) * (x - p.x) / (q.x - p.x);

if (abs (p.x - q.x) < EPS) return p.y;

double get_y (double x) const {

MAXimal :: algo :: Поиск пары пересекающихся отрезков алгоритмом заметающей прямой (sweep line) MAXimal добавлено: 26 Mar 2012 1:00редактировано: 26 Mar 2012 1:00Содержание Поиск пары пересекающихся отрезков алгоритмом заметающей прямой за O (N log N) Даны отрезков на плоскости. Требуется проверить, пересекаются ли друг с другом хотя бы два из них. (Если ответ положителен — то вывести эту пару пересекающихся отрезков; среди нескольких ответов достаточно выбрать любой из них.)Наивный алгоритм решения — перебрать за все пары отрезков и проверить для каждой пары, пересекаются они или нет. В данной статье описывается алгоритм с временем работы , который основан на принципе сканирующей (заметающей) прямой (по-английски: "sweep line"). Алгоритм Проведём мысленно вертикальную прямую и начнём двигать эту прямую вправо. По ходу своего движения эта прямая будет встречаться с отрезками, причём в любой момент времени каждый отрезок будет пересекаться с нашей прямой по одной точке (мы пока будем считать, что вертикальных отрезков нет).Таким образом, для каждого отрезка в какой-то момент времени его точка появится на сканирующей прямой, затем с движением прямой будет двигаться и эта точка, и, наконец, в какой-то момент отрезок исчезнет с прямой.Нас интересует относительный порядок отрезков по вертикали. А именно, мы будем хранить список отрезков, пересекающих сканирующую прямую в данный момент времени, где отрезки будут отсортированы по их -координате на сканирующей прямой.Этот порядок интересен тем, что пересекающиеся отрезки будут иметь одинаковую -координату хотя бы в один момент времени:Сформулируем ключевые утверждения:Для поиска пересекающейся пары достаточно рассматривать при каждом фиксированном положении сканирующей прямой только соседние отрезки.Достаточно рассматривать сканирующую прямую не во всех возможных действительных позициях , а только в тех позициях, когда появляются новые отрезки или исчезают старые. Иными словами, достаточно ограничиться лишь только положениями, равными абсциссам точек-концов отрезков.При появлении нового отрезка достаточно вставить его в нужное место в список, полученный для предыдущей сканирующей прямой. Проверять на пересечение надо только добавляемый отрезок с его непосредственными соседями в списке сверху и снизу.При исчезновении отрезка достаточно удалить его из текущего списка. После этого надо проверить на пересечение с верхним и нижним соседями в списке.Других изменений в порядке следования отрезков в списке, кроме описанных, не существует. Других проверок на пересечения производить не надо.Для понимания истинности этих утверждений достаточно следующих замечаний:Два непересекающихся отрезка никогда не меняют своего относительного порядка.В самом деле, если один отрезок сначала был выше другого, а затем стал ниже, то между двумя этими моментами произошло пересечение этих двух отрезков.Иметь совпадающие -координаты два непересекающихся отрезка также не могут.Из этого следует, что в момент появления отрезка мы можем найти в очереди позицию для этого отрезка, и больше этот отрезок переставлять в очереди не придётся: его порядок относительно других отрезков в очереди меняться не будет.Два пересекающихся отрезка в момент точки своего пересечения окажутся соседями друг друга в очереди.Следовательно, для нахождения пары пересекающихся отрезков достаточно проверить на пересечение только все те пары отрезков, которые когда-нибудь за время движения сканирующей прямой хотя бы раз были соседями друг друга.Легко заметить, что этого достаточно лишь проверять добавляемый отрезок со своими верхним и нижним соседями, а также при удалении отрезка — его верхнего и нижнего соседей (которые после удаления станут соседями друг друга).Следует обратить внимание, что при фиксированном положении сканирующей прямой мы сначала должны произвести добавление всех появляющихся здесь отрезков, и лишь затем — удаление всех исчезающих здесь отрезков.Тем самым, мы не пропустим пересечения отрезков по вершине: т.е. такие случаи, когда два отрезка имеют общую вершину.Заметим, что вертикальные отрезки на самом деле никак не влияют на корректность алгоритма.Эти отрезки выделяются тем, что они появляются и исчезают в один и тот же момент времени. Однако, за счёт предыдущего замечания, мы знаем, что сначала все отрезки будут добавлены в очередь, и лишь затем будут удалены. Следовательно, если вертикальный отрезок пересекается с каким-то другим открытым в этот момент отрезком (в том числе вертикальным), то это будет обнаружено.В какое место очереди помещать вертикальные отрезки? Ведь вертикальный отрезок не имеет одной определённой -координаты, он простирается на целый отрезок по -координате. Однако легко понять, что в качестве -координаты можно взять любую координату из этого отрезка.Таким образом, весь алгоритм совершит не более тестов на пересечение пары отрезков, и совершит операций с очередью отрезков (по операций в моменты появления и исчезновения каждого отрезка).Итоговая асимптотика алгоритма составляет, таким образом, . Реализация Приведём полную реализацию описанного алгоритма:const double EPS = 1E-9;