На плоскости расположены n предметов, их нужно переместить в заданные n позиций. Как это сделать?

Question

[carp123]

На плоскости расположены n предметов, их нужно переместить в заданные n позиций. Неважно, какую позицию какой предмет займёт. Для каждого предмета известна максимальная скорость, с которой его можно перемещать, при этом можно перемещать все предметы одновременно.

Найдите минимальное время, за которое все предметы можно переместить на заданные места.

Входные данные
В первой строке записано целое число n (1 ≤ n ≤ 50).

В следующих n строках записано по 3 целых числа – координаты и максимальная скорость предмета.

В следующих n строках записаны по 2 целых числа – координаты финальных позиций.

Все координаты лежат в диапазоне от 0 до 1000, скорость – от 1 до 1000.

Выходные данные
Выведите одно вещественное число – минимальное время, за которое можно переместить предметы. Погрешность не более 10 - 4.

Comments

[carp123]

Это не для олимпиады, а для себя. Решите пожалуйста(

[Сергей П]

carp123, а для чего вам готовое решение? Хотя бы попытайтесь. Что у вас не получается? Где застопорились? Как рассуждали?

[carp123]

Все как Вы сказали я сделала, но он ведь может ходить и на искосок. Поэтому у меня некоторые тесты какие есть не проходит(

[carp123]

Сергей Паньков, Все как Вы сказали я сделала, но он ведь может ходить и на искосок. Поэтому у меня некоторые тесты какие есть не проходит( Пишу на питоне

[U235U235]

carp123, о чем вы? кто может ходить наискосок?

[Сергей П]

Причем тут наискосок или не наискосок. У вас каждый вариант перемещения точки из всех N**2 - это sqrt((x2-x1)**2+(y2-y1)**2). Не важно наискосок или не наискосок. Это метрика.
Заодно можете поделить это расстояние на скорость точки и получите время перемещения точки.
Итак, у вас N**2 троек: Номер_исходной__точки, Номер_целевой_точки, время.
Вам нужно из этого списка выбрать ровно N элементов, чтобы в них исходные и целевые точки не повторялись и при этом сумма времён была минимальной.
Типичное применение динамического программирования.

[carp123]

Сергей Паньков, ох, в дп ничего не понимаю. Пытался решить линейно

[Сергей П]

carp123, ну может и хрен с ней, а?
Оно вам надо?=)
Да и какая теперь разница? Какой смысл увидеть готовое решение, когда при этом вы лишитесь удовольствия когда-нибудь решить ее самостоятельно.

[Сергей П]

Подсказочка. Заполните матрицу N*N временами движения точки из i в j-ю позицию.
Решайте как судоку.

[carp123]

Сергей Паньков, такая разница, что это может попасться на контрольной или проф экзамене, а я даже это решить не могу. и судоку не понимаю и не знаю

[Сергей П]

может попасться на контрольной или проф экзамене

carp123, ну тогда решение конкретно только этой задачи вам не поможет. Нужно осваивать учебный материал для которого эта задача прилагается как способ проверки знаний.
Наверно в изученном курсе вы решали подобные задачи.

Answer 1

[Сергей П]

Ну вы бы хотя бы присказку какую-то добавили о том как рассуждали, что у вас не получилось и всё такое.
А-то вот решите мне эту задачу, а я думать совсем не хочу.

Давайте, учитесь уже рассуждать. Задачка несложная, видимо олимпиадная, но для каких-нибудь девятых-десятых классов. Хотя че-то, помнится, там посложнее были.

Вот у вас есть 50 точек. И ещё 50 точек. Между каждой парой из них (а пар 50 в квадрате) есть какое-то расстояние. Там написано, что точки на плоскости, а значит расстояния между точками вас учили считать в школе по теореме пифагора.
Если знаете расстояние между точками и знаете скорость каждой точки, значит можно посчитать время.
Осталось что?
Ну думайте.
Этот ресурс не для того, чтобы двоечникам помогать.
Возможно ваши соперники по олимпиаде сейчас сами думают, а вы, позорник, тут халтурите.

Answer 2

[Wataru]

Как вам уже написали, очень просто получить матрицу нужного времени для перемещения каждого предмета в каждую точку по отдельности (расстояние по теореме Пифагора делить на скорость объекта). Теперь вам надо найти такое минимальное время, что для каждого предмета можно выбрать уникальную точку, до которой время перемещения не больше заданного.

Отсортируйте все N^2 времен. Запустите по ним бинарный поиск. В качестве проверки запускайте алгоритм Куна для поиска максимального паросочетания, если оно оказалось полным - текущая граница подходит или слишком большая. Если максимальное паросочетание не полное - граница слишком мала.
Это решение за O(N^3 log N)

Альтернативное решение - отсортируйте все времена и добавляйте соответсвующее паре точек ребро в граф. Ищите дополняющий путь (обход в глубину из алгоритма куна). Если нашли - расширяйте паросочетание. Как только паросочетание стало полным, последнее добавленное - ребро ваш ответ. Это решение за O(N^4). Для N<50 тоже подходит.

Нужно знать: Графы, обход в глубину, паросочетание в двудольных графах (алгоритм Куна, например), бинарный поиск.

Comments

[carp123]

Честно, до меня дошло все это. Но как реализовать правда не знаю. Помогите пожалуйста

[Wataru]

carp123, Как так вообще? Что вы не можете реализовать? Подсчитать времена в матрице для каждой пары объект-точка можете? Выделить их в отдельный массив и отсортировать? Бинарный поиск написать не можете? Построить матрицу из нулей и единиц, где единицы стоят там, где время не больше заданного? Запустить алгоритм Куна на этой матрице?

Вот пример бинарного поиска.
Только вместо сравнения элементов в условии вам надо запускать вашу функцию, которая строит матрицу из 0 и 1, запускает паросочетание и сравнивает его размер с n.

Вот пример реализации алгоритма Куна Правда, там граф задан списком смежности, а не матрицей смежности, но это просто поменять for в функции try_kuhn. Еще там используется k для правой доли, но у вас там тоже должно быть n.

[Сергей П]

Честно, до меня дошло все это. Но как реализовать правда не знаю. Помогите пожалуйста

carp123, что именно? Вам расписали все шаги. В каких именно местах у вас сложности? Задавайте конкретные вопросы.