Задача №3396. Почта
В городе \(\pi\) планируется проведение реформы доставки почты. Вместо большого количества устаревших автомобилей приобретён специализированный Е-мобиль, задача которого — развозить всю корреспонденцию по почтовым отделениям города.
IT-отдел городской почты разработал кольцевой маршрут, проходящий через все почтовые отделения. Все улицы в городе \(\pi\) с односторонним движением. Необходимо выбрать почтовое отделение для размещения логистического центра, куда будет поступать вся городская корреспонденция перед её отправкой на Е-мобиле по маршруту. Из-за пробок скорость движения на участках маршрута между почтовыми отделениями зависит от времени суток. Размещение логистического центра считается оптимальным, если после отъезда из него в нулевой момент времени Е-мобиль развезёт корреспонденцию и возвратится в логистический центр как можно раньше. Время разгрузки корреспонденции пренебрежимо мало.
Требуется написать программу, которая по заданному маршруту с учетом скорости движения Е-мобиля определяет оптимальное расположение логистического центра и наиболее ранний возможный момент возврата в логистический центр.
В первой строке задаётся целое положительное число \(N\) — количество почтовых отделений в городе \(\pi\). Почтовые отделения нумеруются в порядке их следования по маршруту, начиная с единицы.
В следующих строках описаны N участков маршрута между почтовыми отделениями. Каждое описание содержит три строки:
в первой строке описания задаётся целое положительное число \(d_i\) — длина данного участка (\(d_i \leq 10^9\)), а также целое неотрицательное число \(E_i\) — количество отрезков времени, в течение каждого из которых скорость движения Е-мобиля постоянна;
во второй строке даны целые положительные числа \(t_{i,j}\) (\(1 \leq j \leq E_i\), \(0 < t_{i,1} < \dots < t_i,E_i \leq 10^9\)) — значения моментов времени, в которые изменяется скорость движения. Если соответствующее \(E_i\) равно нулю, то эта строка — пустая;
в третьей строке целые положительные числа \(v_j\) – скорости на полуинтервале времени \([t_{i,j-1}, t_{i,j})\), где \(1 \leq j \leq E_{i+1}\), считается, что \(t_{i,0} = 0\), \(t_i,E_{i+1} = + \infty\).
Все числа в строках разделяются одним пробелом.
В единственной строке необходимо вывести номер почтового отделения, в котором нужно разместить логистический центр, а также время проезда Е-мобиля по маршруту.
Ответ должен иметь абсолютную или относительную погрешность не более \(10^{-6}\), что означает следующее. Пусть максимальное расстояние от выведенной точки до некоторой трассы равно \(x\), а в правильном ответе оно равно \(y\). Ответ будет засчитан, если значение выражения \(|x - y| / max(1, |y|)\) не превышает \(10^{-6}\).
В данной задаче три подзадачи.
В тестах первого набора количество почтовых отделений \(N \leq 1000\), \(N \leq \sum_{i=1}^N E_i \leq 1000\). Баллы за первую подзадачу начисляются только в том случае, если все тесты для этой подзадачи пройдены.
В тестах первого набора количество почтовых отделений \(N \leq 4000\), \(N \leq \sum_{i=1}^N E_i \leq 10^5\). Баллы за первую подзадачу начисляются только в том случае, если все тесты для этой подзадачи пройдены.
В тестах первого набора количество почтовых отделений \(N \leq 10^5\), \(N \leq \sum_{i=1}^N E_i \leq 3\times 10^5\). Каждый тест для третьей подзадачи оценивается отдельно.
2 3 2 1 1 2 4 2 2 3 1
2 2.833333333333333
2 2 1 2 2 1 2
1 2.000000000000000