Задать вопрос
@ZelibobA1706
программирование

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

Итак, есть задача: где-то в океане есть острова, с заданными координатами x1, y1, x2, y2. Нужно найти минимальную длину доски для путешествия на любой остров. Острова располагаются только вдоль осей координат. Столкнулся с проблемой нахождения кратчайшего расстояния от одного острова до другого. Т.е. я представляю, что нужно построить граф и потом найти просто самое длинное ребро, но не пойму как получить длину ребра.
  • Вопрос задан
  • 382 просмотра
5 комментариев
Подписаться 1 Оценить 5 комментариев
Пригласить эксперта
Ответы на вопрос 1
@andray15
Тут должен помочь метод координат. Сначала надо найти расстояния между углами, а потом сравнить их с расстояниями между краями "островов". Потом надо найти расстояние между двумя параллельными прямыми - границами островов. Эти границы будут заданы (X0;Y0) и (X1;Y1) - противоположные углы прямоугольника, потом находим 2 других угла - (X1;X0) и (Y0;Y1). Так же получаем координаты второго острова, потом ищем такие границы островов, чтобы их можно было соединить отрезком, который будет перпендикуляром для этих границ, и найти длину этого перпендикуляра.
Ответ написан
7 комментариев
7 комментариев
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
Python developer
Bell Integrator
До 350 000 ₽
Разработчик программного обеспечения авионики
Котлин-Новатор • Санкт-Петербург
от 50 000 до 150 000 ₽
Ведущий разработчик программного обеспечения авионики
Котлин-Новатор
от 150 000 до 250 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Подключить сервер к сети
27 апр. 2024, в 02:39
1000 руб./за проект
Необходимо сверстать приложение согласно макету Figma используя React
26 апр. 2024, в 22:22
1500 руб./за проект
Написать модуль подключения матрицы Sony к ПЛИС (Verilog)
26 апр. 2024, в 21:30
15000 руб./за проект
Ещё заказы