TeXpertКаждому отрезку сопоставляем множество (обозначим его через A(i), где i -- номер этого отрезка) номеров отрезков, с которым этот отрезок пересекается. И как хранить такое множество? Вы помните, что отрезков не три с половиной штуки, а 200'000'000?


Одно из эффективных решений задачи предложено в книге "Алгоритмы: построение и анализ" (Кормен Т., Лейзерсон Ч., Ривест Р.) (стр 375, Дерево отрезков)

Важный момент не был озвучен: как часто меняются данные? Ведь, для статичных и для часто меняющихся данных могут быть совершенно разные решения.

TeXpert Vladimir Sitnikov И как хранить такое множество? Вы помните, что отрезков не три с половиной штуки, а 200'000'000? Читай внимательно -- я об этом знаю
прочитал внимательно. Оказалось, сам алгоритм тоже смысл не особый имеет.

У меня всего лишь пара "простых" вопросов:
1) TeXpertТо есть, в цикле очередной отрезок проверяем на пересечение с оставшимися
Можно подробнее озвучить алгоритм проверки на пересечение двух отрезков?
Это что-нибудь похожее на
или всё-таки более умное?

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

2) Даже, если вы поведаете как реализовать 1-ый пункт (а это очень интересно послушать! без шуток! ведь, это и есть почти та задача, которую просит решить автор). Информация о том, что "отрезок i пересекается с отрезком j" всё равно не даёт мало информации для ответа на поставленую задачу.
Более того,

Контрпример для вашего алгоритма:
один отрезок с координатами (-10, 10)
миллион отрезков с координатами (0,10) (если хотите, у каждого отрезка координаты могут отличаться, но все они положительные, и пересекаются с 1-ым)

проверяемая точка x0 = -5.
Правильный ответ -- один отрезок (-10, 10)
Если я правильно понял ваш алгоритм, то он предложит проверять "дополнительное множество", в которое попадает ещё миллион отрезков. Т.е. миллион действий зря.

3) TeXpert При проверке того, каким отрезкам принадлежит точка x0,последовательно проверяем отрезки на предмет содержания этой точки x0: как только поймаем первый такой отрезок, раскручиваем его вспомогательное множествоА, если мы "поймаем" его лишь в самый последний момент или вообще не поймаем?
Т.е. ваш алгоритм гарантированно потребует перепроверку всех 200'000'000 отрезков, если ни один из них не проходит через точку x0.
Зачем тогда это вспомогательное множество вообще нужно?

3) TeXpert нубпрогМожно строить любые индексы, дополнительные таблицы или все что нужно То есть, для автора это не проблема. Так что, будь внимателен, прежде чем смеятьсяСомневаюсь, что для автора не будет проблемой перерабатывать 100Тб данных, если их вдруг потребует чей-то алгоритм. Давайте учитывать, что бесконечных объёмов памяти и бесконечнобыстрых процессоров не бывает.

TeXpertАфигеть... Для проверки пересечения двух отрезков надо что-то умное изображать? А про "больше года" -- это надо, наверное, постараться... Вкратце: есть координаты концов отрезков на прямой, тут даже придумывать нечегоНаучитесь думать, прежде чем что-либо говорить. Для того, чтобы проверить каждый отрезок на предмет его пересечения со всеми остальными потребуется 200'000'000 * 200'000'000 = 40'000'000'000'000'000 операций.
Современные процессоры работают на частоте порядка 1Ггц == 1'000'000'000 операций в секунду.

Надеюсь, вы в состоянии правильно поделить одно на другое и перевести из секунд в сутки/года?

TeXpertА насчёт Vladimir SitnikovДавайте учитывать, что бесконечных объёмов памяти и бесконечнобыстрых процессоров не бывает так у автора сама постановка такая -- он нас не ограничивает:)). Ведь ясно, что там такая причудливая конфигурация отрезков может оказаться, что придётся считать годами (если дисковой памяти не хватит, а это может запросто случиться). Так что, придётся решать задачу в теоретической плоскости
Когда освоите алгоритм из "Алгоритмы: построение и анализ", можно будет и пофантазировать, но, если я не ошибаюсь, то тому алгоритму нужно было ~4N памяти (порядка 5-10Гб для 200'000'000 отрезков).

И время работы алгоритма (ответ на вопрос "а существует ли отрезок, проходящий через точку x0?") не O(N), а O(Log(N)) вне зависимости от конфигурации отрезков.