Где тут трехмерность ?
вот тож, не ту специальность выбрали )))
Где на массажиста учат? С понедельника пойду.
Нелогично.
Имеем несколько отрезков на плоскости xy.
Каждый отрезок представляем обычным линейным уравнением aX+C=Y
А далее последовательно находим методом перебора точки пересечений прямых, решая систему уравнений из двух прямых. Если решение есть, значит, пересечение есть, переходим к следующей системе уравнений, беря от предидущей второе уровнение, и добавляя следующее.
каждый отрезок имеет начало x1,y1 и конец
x2,y2, имея массив отрезков можем посследовательно искать соответсвия, например первый отрезок должен иметь координату начала x1=0, y1, следующий должен иметь начало (x1=x2,y1=y2) x2,y2 относятся к предидущему отрезку и так пока не достигнем отрезка с x2 больше или равно длина области, если отрезки не параллельны осям X или Y приводим отрезки к прямым вида Ax+By+C=0, для нахождения точки пересечения решаем систему, если x (или y) точки пересечения соответствует отрезку x1<=x<=x2 отрезки пересекаются - продолжаем
кмк , надо все же проверить пересечение всех отрезков со всеми ,что бы знать с какго отрезка на какой можно перейти .
кстати, если сделать матрицу пересечений отрезков ,т.е. написать некую М[k,k] , где 1<i,j<k , M[i,j] = 1 если два отрезка пересекаются.
а потом (это я уже смутно помню про Markov Chains ? - тут уже более серьезные дедушки подскажут ),если возводить эту матрицу в степень , можно знать ,за сколько шагов , и можно ли попась из отрезка d к t ? но цепочки маркова, алгоритм дайкстры и теория графов, это не может быть решением задачки в школе. должно быть более простое и красивое решение.
из задачи вобще не ясно , там где 1 отрезок кончается , может начинаться какой либо другой(тогда решение тривиально) ,или же второй отрезо может начинатся где угодно , и надо самому посчитать есть ли пересечение отрезков в произвольной точке , и предполагая что по таким произвольным пересечениям можно переходить с отрезка на отрезок , заключить можно ли перебраться с одной стороны на другую.
чойта “не может”? я, в 1985 брал 2ое место на городской по программированию. задачки на связность графа самые типичные. писал на Паскале.
так то примитивная задача на связность. и Ркита тут зря пнули - Дейкстра тоже подходит для проверки связности.
в СССР лучшее заведение было в Ессентуках
Не выйдет.
Это уравнение бесконечной прямой.
А отрезок гораздо удобнее задавать координатами концов. При этом имеется вся необходимая информация. В том числе элементарно считается уравнение прямой, на которой лежит отрезок.
Ну и без особенностей записываются случай вертикального отрезка.
Вообще по поводу сообщений 26-28: объясните мне, какое отношение ко всему этому имеет
из условия задачи.
Почему поле дискретно и имеет конечное число точек?
Это приближено к реальным компьютерным графическим делам. Олимпиада же по программированию, а не математике.
1 лайк
Хм…, а это же упрощает задачу.
По опыту речь в задании идёт об ортогональных отрезках.
На первых двух парах проход есть, а на третьей паре нет.
Если бы я знал участников ранее, по форуму, то подумал бы над коллективным опьянением…
n x m тут не причем. Есть конечное множество (из К) отрезков - это вершины графа. Ребра графа - наличие пересечения отрезков. За О(К**2).
Потом работаем с этим графом, забыв про n x m . Стороны с которой и на которую нужно перебраться это отрезки ((0,0),(0,m)) и ((n,0),(n,m)). Они должны находиться в одной связной области. Всё. И для проверки этого есть стандартные алгоритмы, но Дейкстра тоже подходит. Объяснять как?
вы забыли про школьность задачи
еще как причем.
допустим у тебя область m x n = 10 x 10 клеток .
а твои k отрезов образуют многоугольник кторый можо вписать в окружность (х-2)^2 + (y-2)^2 = 2…муравъем , перебраться от одного края к другому ты не сможешь
Повторю медленно: в 1985 году я был в 10 ом классе (не помню была весна или осень, весной - в 9, осенью уже в 10) и принимал участие в городской олимпиаде по программированию. Занял 2ое место. Получил в подарок книгу “Проектирование и конструирование компиляторов” автор Хантер.
ШКОЛЬНАЯ олимпиада. Еще раз ШКОЛЬНАЯ. Теория графов - одна из любимых тем олимпиадных задач. В то время. Школа - математическая, ессно.
Стороны с которой и на которую нужно перебраться это отрезки ((0,0),(0,m)) и ((n,0),(n,m)). Они должны находиться в одной связной области
Чукча не читатель? 
точно , проморгнул после “n x m тут не причем”