Какой алгоритм применить для решения задачи о робинзоне?

Question

[ZelibobA1706]

Итак, есть задача: где-то в океане есть острова, с заданными координатами x1, y1, x2, y2. Нужно найти минимальную длину доски для путешествия на любой остров. Острова располагаются только вдоль осей координат. Столкнулся с проблемой нахождения кратчайшего расстояния от одного острова до другого. Т.е. я представляю, что нужно построить граф и потом найти просто самое длинное ребро, но не пойму как получить длину ребра.

Comments

[ZelibobA1706]

Что если брать два "острова" - прямоугольника и смотреть из каждого угла прямоугольника 1 расстояния до каждого угла прямоугольника 2, а потом находить минимальное значение?

[MiiNiPaa]

ZelibobA1706: Не покатит. У прямоугольников (0,0),(1,2) и (2,1),(3,3) кратчайшее расстояние между углами — sqrt(2), а реальное кратчайшее расстояние — 1

[ZelibobA1706]

MiiNiPaa: ну значит еще добавить расстояние до ребра. Только как? Смотреть находятся ли два смежных ребра на одном уровне?

[MiiNiPaa]

ZelibobA1706: Да, смотреть, есть ли смежные рёбра. Если есть — мерять расстояние между ними, иначе — между ближайшими углами.

[ZelibobA1706]

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

Answer 1

[andray15]

Тут должен помочь метод координат. Сначала надо найти расстояния между углами, а потом сравнить их с расстояниями между краями "островов". Потом надо найти расстояние между двумя параллельными прямыми - границами островов. Эти границы будут заданы (X0;Y0) и (X1;Y1) - противоположные углы прямоугольника, потом находим 2 других угла - (X1;X0) и (Y0;Y1). Так же получаем координаты второго острова, потом ищем такие границы островов, чтобы их можно было соединить отрезком, который будет перпендикуляром для этих границ, и найти длину этого перпендикуляра.

Comments

[ZelibobA1706]

Я делал так: смотрел находятся ли обе фигуры на одном уровне по х или у, если да, то смотрел расстояние между ребрами, а если нет считал по Пифагору расстояние до углов и выбирал минимальное. А по само решение у меня что-то полностью все тесты не проходит, к сожалению не знаю входных данных.

[andray15]

ZelibobA1706: можешь код скинуть?

[ZelibobA1706]

andray15: pastebin.com/bLcDssxM

[ZelibobA1706]

andray15: https://pp.vk.me/c631917/v631917063/33097/JDFyG9bv... задача.

[andray15]

ZelibobA1706: как-то код я не особо понял, но ты правильно понял, что координаты (x0;y0) (x1;y1) - координаты противоположных углов прямоугольника, и подаются в виде четырех чисел

[ZelibobA1706]

andray15: в функцию подается два массива(фигуры) в каждом по 4 координаты, творится магия, с помощью этой функции создается матрица смежности графа, потом алгоритм Прима находит минимальное остовное дерево, ну и из этого дерева выбираем максимальное ребро.

[ZelibobA1706]

andray15: но код стремный, это да.