Просится примерно такое направление действий.
Отрезки нужно разбить на группы, в которых каждый участник пересекается минимум с одним другим участником. Группа состоит из одного или более участника. Формирование группы идёт в несколько этапов - взять любой отрезок, все отрезки, пересекающиеся с ним, добавить к нему в группу, для каждого добавленного повторить поиск и добавление. После завершения формирования группы проверить по крайним точкам является ли она решением (путём от края до края). Возможно делать проверку после каждого добавления отрезка в группу. Если формирование группы закончено и она не является решением - все отрезки группы выкидываем нафиг. Собираем следующую, если осталось из чего.
Вряд ли оптимально, но к ответу вроде должны прийти.
Чего именно Вам не хватает?
правил движения муравья насколько близко должны быть точки что бы муравей пролез, расположения плоскости горизонтальо или вертикально, так если бы не было муравья, а просто соединение сторон ломаной линией…
Я рассужу, т.к. имел отношение к проведению подобных олимпиад разного уровня (вплоть до международных) многие годы.
В подобных задачах всегда, если явно не оговорена обратное, отрезки имеют нулевую толщину (как и математические отрезки, кстати). В нашем случае координаты концов целые, а потому:
Все надуманности про (не)проходимость прямой Брезенхэма - это горе от ума. Не надо выпендриваться, выдумывать сущности и всё усложнять.
Ни на сколько - точки должны совпадать (отрезки пересекаться). Если между точками хоть какое-то расстояние, он не проходит.
но это же ваше утверждение, а не автора задачи, возможно его муравей не такой как у всех остальных (вообще зачем включают такого рода цацки в задачи?)
Это утверждение человека, который десятки раз готовил и проводил олимпиады, а также десятки раз участвовал в разборе апелляций участников. Я знаю такие задачи, уж поверьте.
да, несомненно, вы знаете задачи, и я с вами согласен, но просто не факт что в уездном городе Н не решили чего-нибудь модернизировать, а для себя я алгоритм как бэ нащупал
да неважно что там допридумали , какой толщины отрезки и какой длины муравей и может ли он прыгать и звать кого на подмогу…
то что описано в задаче - достаточно для ее решения…вопрос , можно ли решить эффективней и красивей чем через теорию графов(дракул)
о графах я знаю только что они есть и у нас были до Революции
Что Вы понимаете под:
Если алгоритм Дейкстры, о котором тут упоминали, так он здесь избыточен, т.к. он для другой задачи: “найти кратчайший путь”. У нас же надо только сказать есть путь или нет. Ни находить его, ни доказывать его “кратчайшесть” не нужно.
Если же “метод волны”, то сам по себе метод простой как валенок … Вы можете использовать при этом графовые термины или не использовать и всё объяснить на пальцах … помните как г-н Журден был весьма удивлён, когда узнал, что он всю жизнь говорил прозой.
имею ввиду,что если ограничиться вопросом “можно ли пересечь?” ,как вы исказали и как было изнчально в условии задачи ,а не “каков кратчайший путь,если он есть”(на что отвечает Дайкстра) , можно ли решить задачу за линейное время или за nlog(n) ?
можете,пожалуйста , дать ссылку где почитать про “метод волны” именно в контексте “есть маршрут или нет” ?
Точно, нет.
Не знаю. Тут надо думать и объём этого думания явно выходит за рамки того, что я мог бы этому вопросу уделить 
- “Дейкстра”, конечно, избыточен. Я сказал, что он подходит, после того, как “пнули” Ркита. Хотя он и правда подходит. Если индекс вершины менее бесконечности - она достижима. Это же очевидно.
- n log n - я не вижу. Для наличия решения nlogn нужно какое-то естественное упорядочивание объектов задачи - наших отрезков, наличие естественно способа индексации. То, что я его не вижу, не значит, что его нет вовсе. Но интуитивно - не вижу.
Меньше то оно меньше, вот только цели не достигает.
В данной задаче явно указано конечное число точек m*n, как это сказывается на решении?
Вопрос не в том, какие задачи лично Вы знаете. Вопрос в том, как эту задачу следует воспринимать школьнику, который не имеет возможности задать Вам вопросы, проясняющие условие задачи.
Если задача сформулирована некорректно, все сомнительные вопросы должны разрешаться, исходя из интересов школьника, но никак не из личного опыта кого-то из организаторов.
И самое главное - легко изобретаем на уровне школьника-олимпиадника.
С чего? Уточняющие вопросы по условию всегда задавались.
Данная задача сформулирована вполне корректно. Слово “отрезок” по определению из школьного учебника - часть прямой, между двумя лежащими на ней точками. Прямая (а, стало быть, и отрезок) не имеет толщины и абсолютно прямолинейна. А то, что Вы с командиром притянули сюда “толстые отрезки” и ломаные Брезенхэма - это от нечего делать и от большого желания придраться, заодно показав свой кругозор. То, что нарисовали командир и Вы отрезками не является.
Если он знает определение отрезка, то по определению, а если не знает, то с какого бодуна это должно разрешаться в его пользу?
P.S. И, да, кстати, я согласен, что в задаче не оговорена спортивная подготовка муравья. Может он через пять линий прыгать умеет, у кузнечика научился. Но, на эту тему я уже тут говорил:
Да?
И как, интересно, это технически осуществить?
Вот пришел школьник в свою школу на олимпиаду, преподаватель по информатике огласил присланные условия задач (пусть даже раздал листочки с условием и e-mail’ом организаторов). Условие вызвало у школьника вопрос. Преподаватель на этот вопрос ответить не смог. Что дальше делать школьнику?
Мы этого не знаем.
Если Вы располагаете корректной формулировкой, опубликуйте ее пожалуйста.
То, что написано в первом посте темы вызывает вопросы.
В частности, непонятно, как использовать информацию о поле n на m.
Ну так и олимпиада не по геометрии, а по программированию.
С точки зрения растрового устройства отображения информации (дисплея) - вполне себе отрезки. И, кстати (для тех, кто изучает в школе не только математику, но и английский), называется “Line”, которая, вроде бы, должна иметь нулевую толщину, но ни на бумаге, ни на дисплее так почему-то не получается.
Сами же прекрасно знаете, что в школьной программе по математике число - это одно, а в программировании число - это совсем другое. Почему для отрезков должно быть какое-то исключение?
Не нужно собственные ошибки и небрежность в формулировке задач сваливать на школьников, обвиняя их в занудстве.
И, возвращаясь к прежним постам. Вот это:
Ни разу не норма.