시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 2 | 1 | 1 | 50.000% |
Власти Флатландии решили построить новый мост через реку Нижний Флат, протекающую с юга на север через территорию страны. В связи с финансовым кризисом средства строителей существенно ограничены, поэтому решено было построить мост минимальной возможной длины.
Введем координатную систему таким образом, чтобы ось $OY$ была направлена с юга на север, а ось $OX$ --- с запада на восток. Берега реки представляют собой ломаные, бесконечные в обе стороны. Левый берег начинается лучом, направленным на юг из точки $(x_{1,1}, y_{1,1})$, продолжается отрезками $(x_{1,1}, y_{1,1})-(x_{1,2}, y_{1,2})$, $(x_{1,2}, y_{1,2})-(x_{1,3}, y_{1,3})$, \dots, $(x_{1,m-1}, y_{1,m-1})-(x_{1,m}, y_{1,m})$ и заканчивается лучом, направленным на север из точки $(x_{1,m}, y_{1,m})$. Аналогично, правый берег реки начинается лучом, направленным на юг из точки $(x_{2,1}, y_{2,1})$, продолжается отрезками $(x_{2,1}, y_{2,1})-(x_{2,2}, y_{2,2})$, $(x_{2,2}, y_{2,2})-(x_{2,3}, y_{2,3})$, \dots, $(x_{2,n-1}, y_{2,n-1})-(x_{2,n}, y_{2,n})$ и заканчивается лучом, направленным на север из точки $(x_{2,n}, y_{2,n})$.
Помогите руководству Флатландии выяснить, мост какой минимальной длины можно построить.
Первая строка входного файла содержит целое число $m$ ($2 \le m \le 100$). Следующие $m$ строк содержат по два целых числа --- координаты вершин ломаной левого берега: $x_{1,1}, y_{1,1}$, $x_{1,2}, y_{1,2}$, \dots, $x_{1,m}, y_{1,m}$.
Следующая строка входного файла содержит целое число $n$ ($2 \le n \le 100$). Следующие $n$ строк содержат по два целых числа --- координаты вершин ломаной правого берега: $x_{2,1}, y_{2,1}$, $x_{2,2}, y_{2,2}$, \dots, $x_{2,n}, y_{2,n}$.
Известно, что $x_{1,1}<x_{2,1}$, каждая из ломаных не имеет самопересечений и самокасаний, ломаные не имеют общих точек. Все отрезки каждой из ломаных имеют положительную длину. Все координаты не превосходят $10^4$ по абсолютной величине.
Выведите в выходной файл одно вещественное число: минимальную возможную длину моста. Ваш ответ будет проверяться с точностью $10^{-5}$.
4 6 1 3 1 3 0 0 3 3 9 3 2 3 6 5
1.41421356237309505
Оптимальное положение моста показано на следующем рисунке: