Задача №113295. Уборка снега
В Лайнландии есть одна очень важная дорога, имеющая форму прямой на плоскости. Зимой дорогу часто засыпает снегом, и коммунальные службы стараются оперативно ее очищать.
Лайнландские метеорологи предсказали, что сегодня ночью пройдет снегопад. Они даже в точности смогли описать его ход. Ровно в полночь над страной сформируется облако, из которого будет непрерывно падать снег. Можно считать, что облако представляет собой выпуклый многоугольник, если смотреть на него сверху.
Также метеорологи прогнозируют очень сильный и изменчивый ветер. Благодаря этому ветру траекторией движения облака будет ломаная. Движение облака за ночь можно разбить на несколько участков. Каждый участок задается вектором перемещения облака, во время перемещения вдоль участка облако движется прямолинейно, при этом каждая точка облака перемещается на заданный вектор, облако не меняет форму и не поворачивается.
Каждая точка дороги, над которой пролетит облако, будет покрыта снегом. Коммунальные службы хотят как можно быстрее расчистить дорогу от снега. Для этого они хотят знать общую длину дороги, которая окажется покрыта снегом с утра. Помогите им найти эту величину.
Рисунок показывает перемещения облака и покрытую снегом часть дороги в первом примере.
В первой строке содержится описание дороги. Она задается двумя различными точками, которые на ней лежат. Каждая точка описывается двумя целыми числами \(x, y\) (\(−10^8 \le x, y \le 10^8 \)).
Далее следует описание облака в виде выпуклого многоугольника. В первой строке записано целое число \(n\) — количество вершин многоугольника (\(3 \le n \le 10^5\) ). В следующих \(n\) строках содержится описание положения облака в полночь, каждая строка содержит два целых числа \(x_i\) и \(y_i\) — начальное положение \(i\)-й вершины (\(−10^8 \le x_i , y_i \le 10^8\) ). Вершины заданы в порядке обхода многоугольника против часовой стрелки.
В следующей строке задано целое число \(m\) — количество изменений направления ветра (\(0 \le m \le 10^5\) ). В следующих \(m\) строках записано, как изменилось положение облака в течение очередного участка времени. Каждый участок характеризуется двумя целыми числами \(dx_i\) и \(dy_i\) — на сколько переместилось облако по каждой координате за время \(i\)-го участка (\(−10^3 \le dx_i , dy_i \le 10^3\) ). Гарантируется, что хотя бы одно из этих двух чисел не равно нулю.
Выведите одно вещественное число — общую длину дороги, которая покрыта снегом. Ответ будет считаться верным, если он имеет относительную или абсолютную погрешность не более \(10^{−9}\) .
0 3 1 3 4 -4 2 -5 2 -5 1 -4 1 2 6 3 2 -4
4.5
0 0 1 1 5 1 -2 3 -2 3 -1 2 0 1 -1 4 -1 1 1 1 -7 0 0 -20
5.65685424949238