Предыстория. Я был школьником увлечённым компьютерами, участвовал в олимпиадах по программированию, на “старости” лет решил вспомнить задачу из одной из этих олимпиад. Было это в далёком 1998 (вроде) году. Попытаюсь восстановить условие задачи, которую я тогда не смог решить, возможно сейчас усложню условия.
Есть “поле” условно n на m точек, n и m задаётся экзаменаторами. Есть отрезки в этом поле, координаты крайних точек отрезков и их количество задаётся экзаменаторами.
Задача выяснить, вот тут мне немного сложно объяснить, попробую, там было про муравья , сможет ли муравей перебраться по этим отрезкам с левой стороны на правую.
А забыл, поле и отрезки должны быть отображены графически. Я тогда попытался через “анализ” пикселей пойти, но не получилось у меня.
Но возможно для решения задачи графическое отображение и не нужно. Вспомнил, графическое отображение было элементом моего решения задачи. )
а теперь можно получить диплом кафедры Прикладная математика и не иметь представления о теории графов )))
PS (трёх ведущих мировых университетов, сами догадаетесь каких)
Хорошо.
По условию у нас поле из конечного количества узлов. Судя по условию, между узлами конец провода находиться не может.
Тогда вопрос: провода (0,1)-(0,3) и (1,3)-(1,5) контачат между собой?
