Я склоняюсь к такому алгоритму:
Не, нет 
Не освежил ещё свои школьные воспоминания о деревьях, бинарные тут не подойдут.
Прочитал условие, подумал, вроде бы задача несложная, но перечитал еще раз и вот благодаря этому:
я понял, что я ничего тут не понял. Что под этим скрывается?
Что за поле такое которое состоит из точек?
Без определения понятий “поле” и “точка” нечего и браться за решение такой задачи.
А как по мне, так условие сформулировано неоднозначно.
Если под точками подразумеваются пиксели (а фраза “поле n на m точек” так и воспринимается), тогда как раз и приходится думать в сторону “толстых отрезков” и Брезенхэма).
Можно конечно предположить, что условие неверно сформулировано и n на m - это просто сетка или даже просто размер поля без никаких точек и все отрезки имеют нулевую толщину. Тогда решаться все будет по другому, а именно как вариант: сначала определяем какие отрезки пересекаются (это обычная математика), т.е. составляем граф и ищем в нем наличие нужного пути.
Но это предположение, а реальная формулировка условия больше предполагает вариант с толстыми линиями нежели иной.
Я ахреневаю! Сколько же тени можно напустить на самый обычный плетень. Тут тебе и “растровое устройство”, и “определения понятий “поле” и “точка”” и хрен его знает чего ещё. Каким боком, откуда - а пофиг
А может все проще - сущность задачи в другом, например оценить необходимое условие величина суммы длин проекций на х отрезков больше или равно m.
Я нашёл условие задачи.
Муравей оказался на берегу большой лужи. На поверхности лужи ветром надуло тростинки. Сможет ли муравей переправиться на другой берег по тростинкам.
Задача: задана лужа полем 10 на 10. Вершины каждой клетки пронумерованы в порядке возрастания слева направо и сверху вниз. Верхний левый угол имеет координаты (0,0). Составить программу, которая по введенным координата концов тростинок (координаты тростинок целые числа) отвечала на вопрос, можно ли с левой стороны попасть на правую сторону лужи и выводила один из возможных путей перехода с левой стороны на правую.
Входные данные: данные вводятся из файла, имя файла вводится с клавиатуры. Файл находится в текущем каталоге.
Структура файла: в первой строчке записано количество тростинок N. Во второй строчке координаты 1-ой тростинки, в третьей строчке - координаты 2-ой тростинки,…,N + 1 строчке находятся координаты концов N тростинки
Пример данных в файле:
4
0 2 5 5
2 3 8 9
2 9 10 5
5 5 5 1
Выходные данные: на экран выводится последовательность номеров тростинок, по которым можно переправиться с левой стороны на правую.
Примечание: в случае неумения работать с файлами, данные можно ввести с клавиатуры в соответствии с примером из условия задачи.
Умный в лужу не пойдёт - умный лужу обойдёт !!!
Читаю ветку и думаю - как хорошо что у меня в школе не было олимпиад по программированию - я бы никогда не начал программировать после такого
Вот ссылка на все задачи той олимпиады.
я же говорил, что знаю эту задачу. 
Это школьная задача тех времен, когда про “толщину линии” никто не задумывался.
А то, панимашь!
ЗЫ:
Б707, а что тебе не понравилось? Хорошая задача на связность графа. О чем я и ЕП тут уже исписались…
Задача даже слишком хороша для меня. Я даже примерно не знаю как ее решать, кроме тупого перебора пересечений атрецков Но это явно не вариант для олимпиады.
Кстати, откуда ты можешь ее знать? В наше время (а у нас с тобой, напомню, разница в возрасте менее месяца) - никакого программирования в школе не было, а потому и олимпиад быть не могло.
Я скопировал со ссылки. Так что это не у меня.
в общем случае пп4…9 тоже займут O( N**2).
??? я в матшколе учился. У меня программирование было. Такшта не надо.
Если интересно, то в сетку часов вписывали, как уроки труда и УПК. Вели у нас ребята из ИПМ. (институт прикладной математики)
Так это тупой перебор, про который я и говорил. С таким решением олимпиаду не выиграть.
Надо “р-р-раз - и в дамки!”
ну после этого о чем с тобой говорить?
“При знакомстве задавайте вопросы в порядке значимости. Если человек не любит алкоголь, то, скорее всего, вам и не надо знать, как его зовут.”
А что, тростинки должны только идеально концом на край лужи падать?
Координаты одного конца тростинки вполне имеют право быть за пределами лужи. Обеих нет - это уже вряд ли можно назвать тростинкой на поверхности лужи, ну и такая тростинка в принципе никакой роли в решении не играет.
Не, это острый перебор. Тут всё за квадратичное время. Тупой перебор («метод британского музея») - это когда за экспоненциальное
На олимпиадах по программированию никогда не оценивается острота или тупость решения. Там нужно просто получить решение. Ничто другое не оценивается. Любой алгоритм, хоть просто печать готового ответа (который устно получен). Есть решение - хорошо.
Тут при решении подобных задач, мне так кажется, самое сложное - это уметь определять всякие N ** 2 и тому подобные O(N ** 2) и выбирать самый оптимальный.
Иначе можно не дождаться результата, даже если решение имеется 
