Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 34
Каждый начинающий олимпиадник в какой-то момент считает, что пересекать отрезки просто. В вашем случае, например, проблема в том, что один из концов отрезка может лежать на другом отрезке, тогда векторные произведения будут нулевые, однако отрезки будут пересекаться. Попробуйте исправить ваш код так, чтобы он проходил все тесты тут: http://informatics.mccme.ru/mod/statements/view3.php?id=1156&chapterid=280#1.
Про упомянутого Вами автора, каюсь, не слышал.
Ну и выпускник я лет уж как 10.
Ну и выпускник я лет уж как 10.
Спасибо за наводку. Вот, нашёл в формате djvu www.proklondike.com/var/file/kormen_leiser_algorith.zip
Нашёл указанный Вами алгоритм в главе 35.
Однако в алгоритме у Кормена никак не находится точка пересечения прямых.
Нашёл указанный Вами алгоритм в главе 35.
Однако в алгоритме у Кормена никак не находится точка пересечения прямых.
Спасибо огромное за ценные указания =)
Но видимо, простите, чукча не читатель, чукча писатель? =)
У меня отдельно разобран случай где векторные произведения нулевые, и указано, что считать это пересечением или нет — дело каждого. В моей конкретной реализации этот пограничный случай пересечением не считается.
Но видимо, простите, чукча не читатель, чукча писатель? =)
У меня отдельно разобран случай где векторные произведения нулевые, и указано, что считать это пересечением или нет — дело каждого. В моей конкретной реализации этот пограничный случай пересечением не считается.
Понятно, простота вашего алгоритма заключается в упрощении задачи. Никогда бы не подумал, что бывают люди, считающие совпадающие отрезки непересекающимися…
Уж простите, что не читал, я увидел вот это:
и совсем забил на чтение статьи сосредоточившись на коде.
Уж простите, что не читал, я увидел вот это:
(|a| |b| sin(ab))
и совсем забил на чтение статьи сосредоточившись на коде.
и совсем забил на чтение статьи сосредоточившись на коде.
Ну как раз в коде это и учитывается как случай отсутствия пересечения.
Никогда бы не подумал, что бывают люди, считающие совпадающие отрезки непересекающимися…
А что в этом такого? А еще бывает такое что конечная точка отрезка вообще в отрезок не входит, смотря какой отрезок. Если Вы математику помните, то обозначения вроде (a, b), [a, b], и их комбинации Вам что-то об этом должны напомнить.
Если Вы математику помните, то обозначения вроде (a, b), [a, b], и их комбинации Вам что-то об этом должны напомнить.
Ни разу не слышал, как (a, b) называют отрезком. Википедия относит к отрезку только [a, b], а (a, b) википедия называет промежутком. Я слышал, как (a, b) называют интервалом, а [a, b) и (a, b] — полуинтервалами, но никогда — отрезками. Но указание вашего учебника математики, в котором это называют отрезками, меня вполне убедит.
Если что, совпадающие отрезки имеют точки пересечения не только в конечных точках, так что очень бы хотелось услышать сколько-нибудь формальное определение пересечения отрезков в котором совпадающие отрезки не пересекаются. Будет совсем здорово, если в этом определении несовпадающие отрезки, которые имеют больше одной общей точки, также не пересекаются.
В плане совпадающих отрезков я Вас услышал. Действительно, я лично не уверен, как их классифицировать. В моём случае стояла задача о пересечении отрезков двух различных прямых, но в общем случае Вы правы.
Соответственно, правильным заголовком будет: «Простой алгоритм пересечения двух интервалов, лежащих на различных прямых». И эта задача решается куда проще.
Первую прямую мы зададим, как A + (B — A) * x, где x — действительное число. Вторую соответственно C + (D — C) * y. Теперь найдем такие x и y, чтобы A + (B — A) * x = C + (D — C) * y. Это и будет точка пересечения, а для проверки принадлежности отрезку (интервалу) надо лишь проверить, принадлежат ли x и y отрезку (интервалу) от нуля до единицы. Доказательство тривиально.
Первую прямую мы зададим, как A + (B — A) * x, где x — действительное число. Вторую соответственно C + (D — C) * y. Теперь найдем такие x и y, чтобы A + (B — A) * x = C + (D — C) * y. Это и будет точка пересечения, а для проверки принадлежности отрезку (интервалу) надо лишь проверить, принадлежат ли x и y отрезку (интервалу) от нуля до единицы. Доказательство тривиально.
Ну во-первых то что вы описали не является алгоритмом. А «найдём такие x и y» подразумевает под собой решение системы двух линейных уравнений.
И, вот, вопрос к вам возник. Является ли пересечением отрезок нулевой длины лежащий на другом отрезке?
И, вот, вопрос к вам возник. Является ли пересечением отрезок нулевой длины лежащий на другом отрезке?
Ну во-первых то что вы описали не является алгоритмом
Является в предположении, что мой собеседник знает, как решается система из двух линейных уравнений с двумя неизвестными с предельно щедрой добавкой о ненулевом детерминанте системы. Лично я это проходил в седьмом классе примерно. Поэтому я предположил, что вам будет неинтересно читать о том, как это делается. Но если интересно, скажите, я объясню, там все довольно тривиально.
Является ли пересечением отрезок нулевой длины лежащий на другом отрезке
Является, если принимать во внимание википедийное определение отрезка. Правда он внезапно целиком лежит на прямой другого отрезка, а значит не очень подходит под условие задачи.
Ну строго говоря он внезапно лежит на любой прямой проходящей через конечные(ную) точки(ку) нулевого отрезка. Поэтому такая конфигурация подходит под условие и той задачи которая ставилась мне.
Ну и я не вижу, чем решение системы уравнений проще двух векторных произведений.
Ну и я не вижу, чем решение системы уравнений проще двух векторных произведений.
Когда я говорил «Лежащих на различных прямых» я имел в виду «Не лежащих на одной прямой», а вовсе не «Существуют две различные прямые такие, что на них можно уложить по отрезку».
Если вы внимательно посмотрите на свой алгоритм, вы поймете, что он не отличает точку лежащую на отрезке и точку, лежащую на прямой, но не на отрезке. Эту разницу просто нельзя вычислить векторными произведениями, которые всегда нулевые, если все лежит на одной прямой.
Строго говоря вычисления более менее одни и те же. Решение системы лучше более простым доказательством и четким пониманием, где оно работает, а где — нет (то, чего так не хватает вашей статье). Ну и бонусом оно нормально работает с отрезками и с многомерными случаями.
Если вы внимательно посмотрите на свой алгоритм, вы поймете, что он не отличает точку лежащую на отрезке и точку, лежащую на прямой, но не на отрезке. Эту разницу просто нельзя вычислить векторными произведениями, которые всегда нулевые, если все лежит на одной прямой.
Строго говоря вычисления более менее одни и те же. Решение системы лучше более простым доказательством и четким пониманием, где оно работает, а где — нет (то, чего так не хватает вашей статье). Ну и бонусом оно нормально работает с отрезками и с многомерными случаями.
Если вы внимательно посмотрите на свой алгоритм, вы поймете, что он не отличает точку лежащую на отрезке и точку, лежащую на прямой, но не на отрезке. Эту разницу просто нельзя вычислить векторными произведениями, которые всегда нулевые, если все лежит на одной прямой.
Ну собственно поэтому я Вам и ответил, что я не учитывал случай отрезков лежащих на одной прямой. Во всех остальных случаях данный алгоритм работать будет.
Вообще говоря, Вы в принципе говорите вещи-то дельные, но Ваш изначально едкий тон совершенно не настраивает на конструктивный разговор.
Попробуйте в следующий раз прочитать собственную статью перед тем, как упрекать других в том, что они ее не читали.
Попробуйте в следующий раз вместо «каждый начинающий олимпиадник» подобрать какое-нибудь более нейтральное обращение, и Вы удивитесь, насколько больше стали прислушиваться к вашим словам.
Если вы видите предложение, в котором обозначена некоторая группа людей, это не значит, что это обращение. Строго говоря, нет никакой четкой зависимости между этим предложением и этим постом: вы нигде не утверждали, что вы олимпиадник и что вы считаете задачу простой (да, там есть утверждение о тривиальности, но я считал, что это относится к формулировке). Причина существования этого предложения в том, что задача про пересечение отрезков имеет огромное количество простых и неправильных решений, а придумать правильное решение без разбора кучи случаев не очень тривиально, поэтому начинающие олимпиадники пишут первый вариант решения за 10 минут и только через 4 часа двадцать пятый вариант оказывается верным во всех случаях. Я видел столько подобных случаев, что очередное частное решение в виде статьи на хабре не может не вызывать у меня улыбку. Очень жаль, что такое невинное предложение вас обидело, я этого сделать не пытался.
В функции использован самодельный шаблон vector<typename, int>, который является шаблоном вектора размерностью int с компонентами типа typename.
Да это ж std::array!
Скажите, а вы всегда плавучку сравниваете при помощи ==?
Скажите, а вы всегда плавучку сравниваете при помощи ==?
Я понимаю о чём вы, но в данном случае учет погрешности смысла не имеет — если Z даже незначительно больше или меньше нуля, он учтется в ветке, где сравниваются знаки.
Как бы вам это сказать… то что числа с плавающей запятой нельзя сравнивать через == учат на первом семестре любого нормального вуза на соответствующем направлении.
Видите ли, иногда то, чему учат в ВУЗах необходимо переосмысливать. Если вы понимаете, зачем существует это правило, значит вы поймёте, почему в данном случае им можно пренебречь.
То что вы проверяете знак не является оправданием. Потому что проверка знака это сравнение с нулем. А сравнение с нулем на вещественных числах тоже делается через введенную точность вычислений. Вы не можете «строго» сравнить с нулем ваше число, т.к. не можете быть уверены что при точности вычислений e, если ваше число меньше e но больше 0, оно точно будет больше 0. Очень странно, что вы не понимаете прописных истин. Нет, конечно если вы берете только «хорошие» случаи, где углы между векторами выражаются в кол-ве градусов больше 1, то на это можно не обращать внимание, но тогда и статью надо было назвать «мое решение задачи с очень ограниченным и практически идеальным набором вариантов». Выше уже писали сколь много случаев вы просто теряете или пренебрегаете ими. Ну вот вам еще один.
Это не совсем std::array, там есть перегруженные операторы и дополнительные функции для работы с векторами.
Не работает в случае нулевого вектора. Вы не сможете проверить на принадлежность полуплоскости, т.к. вы не сможете написать уравнение прямой (иными словами подойдет любое уравнение и что бы вы не подставили всегда будет тождество 0==0). Это действительно нетривиальная задача если рассматривать все а не только очевидные случаи, да еще и с поправкой на формат чисел. Если добавить, что координаты целочисленные, то тогда можно к слову иметь возможность строго говорить о пересечении, совпадении и т.п., т.к. без операций деления мы не выйдем за множество целых чисел (а делить нам нигде не придется, все что при проверках на первый взгляд нужно делить можно преобразовать в операции только умножения).
Все мы что-то изучаем со временем и переоткрываем, не подозревая, что все уже открыто до нас.
Про себя скажу, что для меня это лучший путь решить задачу и понять логику открытия, чем просто подсмотреть в уже готовое решение.
Ощущения не такие!
Еще в университете «изобрел» один простой способ шифрования данных, но только недавно оказалось, что у него уже есть изобретатель и открыт в 70-х годах. Нужно учитывать, что в то время у меня не было интернета под рукой, чтобы за пять минут найти решение стоящей задачи.
Да, классику нужно знать.
Про себя скажу, что для меня это лучший путь решить задачу и понять логику открытия, чем просто подсмотреть в уже готовое решение.
Ощущения не такие!
Еще в университете «изобрел» один простой способ шифрования данных, но только недавно оказалось, что у него уже есть изобретатель и открыт в 70-х годах. Нужно учитывать, что в то время у меня не было интернета под рукой, чтобы за пять минут найти решение стоящей задачи.
Да, классику нужно знать.
Вот кстати из разряда «То, о чем никогда не задумываешься»:
1. Уравнение прямой в общем виде (ax + by + c = 0) можно записать как вектор (a, b, c)
Тогда чтобы найти точку пересечения двух таких прямых — достаточно взять векторное произведение: Cross( (a1, b1, c1), (a2, b2, c2) ). Мы получим однородные координат в которых лежит наша точка пересечения.
2. У нас есть две точки: (x1, y1) и (x2, y2). Чтобы найти общее уравнение прямой, проходящей через эти точки достаточно взять векторное произведение наших точек в однородных координатах: Cross( (x1, y1, 1), (x2, y2, 1) )
Вот такая красивая симметрия в двух измерениях…
1. Уравнение прямой в общем виде (ax + by + c = 0) можно записать как вектор (a, b, c)
Тогда чтобы найти точку пересечения двух таких прямых — достаточно взять векторное произведение: Cross( (a1, b1, c1), (a2, b2, c2) ). Мы получим однородные координат в которых лежит наша точка пересечения.
2. У нас есть две точки: (x1, y1) и (x2, y2). Чтобы найти общее уравнение прямой, проходящей через эти точки достаточно взять векторное произведение наших точек в однородных координатах: Cross( (x1, y1, 1), (x2, y2, 1) )
Вот такая красивая симметрия в двух измерениях…
Не силен в теории, да даже если и знал, то подзабыл.
Коллеги, напомните пожалуйста, как называется вот такое решение:
Приводим отрезки к виду линейных уравнений (вычисляем коэффициенты и смещение), и находим точку пересечения прямых, на которых они лежат.
Если прямые не пересекаются — они параллельны, отрезки параллельны, выход.
Проверяем, принадлежит ли точка пересечения каждому из отрезков (сравниваем коэффициент от точки пересечения до начала отрезка с коэффициентом от конца отрезка до начала отрезка — должны совпасть в какой-то комбинации, в зависимости от угла наклона отрезка). Булев результат является искомым.
Внутри — две элементарные алгебраические операции. Правда, есть деление.
Коллеги, напомните пожалуйста, как называется вот такое решение:
Приводим отрезки к виду линейных уравнений (вычисляем коэффициенты и смещение), и находим точку пересечения прямых, на которых они лежат.
Если прямые не пересекаются — они параллельны, отрезки параллельны, выход.
Проверяем, принадлежит ли точка пересечения каждому из отрезков (сравниваем коэффициент от точки пересечения до начала отрезка с коэффициентом от конца отрезка до начала отрезка — должны совпасть в какой-то комбинации, в зависимости от угла наклона отрезка). Булев результат является искомым.
Внутри — две элементарные алгебраические операции. Правда, есть деление.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простой алгоритм определения пересечения двух отрезков