{"raw_statement":[{"iden":"statement","content":"Фронтмэн известной рок-группы Мэд, заработав на выпуске своего последнего альбома целое состояние, купил себе особняк с колоннами и видом на оживленную улицу. Однако в первое же утро в новом доме он столкнулся с тем, что проезжающие мимо на автомобилях фанаты начинают снимать его на камеры своих телефонов, как только он покажется из-за колонн.\n\nУтром Мэд начинает движение из точки (0,  - 1) и движется параллельно оси OX со скоростью 1 в течение времени T.\n\nНа оси OX расположены N колонн, представляющих собой отрезки шириной W. Для каждого отрезка задана X-координата левой точки Si, x. Отрезки не пересекаются, не касаются друг друга и все концы отрезков находятся в сегменте [0, T] по X-координате.\n\nБесконечная дорога расположена вдоль координаты Cy параллельно оси OX. По дороге движутся K машин со скоростью Cv. Для каждой машины известна X-координата Ci, x в начальный момент времени.\n\nКолонны — непрозрачные. В некоторый момент времени Мэд попадает в кадр видеокамеры, находящейся в машине, если точку, в которой он находится, можно соединить отрезком с точкой, в которой находится машина, не касаясь и не попадая внутрь ни одного из отрезков, соответствующих колоннам.\n\nВ каждой машине находится ровно один фанат с камерой, запись он производит тогда и только тогда, когда Мэд попадает в кадр. Таких периодов может быть несколько, в этом случае и записей у фаната будет несколько. Вечером все фанаты, конечно, выкладывают все свои записи в сеть. Необходимо определить, какое суммарное время будут занимать видеоролики с Мэдом, снятые утром.\n\nВ первой строке задано время движения Мэда T (1 ≤ T ≤ 106), ширина колонн W (1 ≤ W ≤ 106), Y-координата дороги Cy (1 ≤ Cy ≤ 106) и скорость машин Cv ( - 106 ≤ Cv ≤ 106).\n\nВо второй строке задано количество колонн N (1 ≤ N ≤ 2000).\n\nВ третьей строке заданы N чисел Si, x (0 ≤ Si, x ≤ T - W, Si, x + W < Si + 1, x) — упорядоченные по возрастанию X-координаты левых точек отрезков, соответствующих колоннам. Гарантируется, что отрезки не пересекаются и не касаются друг друга.\n\nВ четвёртой строке задано количество машин K (1 ≤ K ≤ 2000).\n\nВ пятой строке заданы K чисел Ci, x ( - 1012 ≤ Ci, x ≤ 1012) — упорядоченные по возрастанию X-координаты машин.\n\nВсе числа во входных данных целые.\n\nВыведите суммарную длительность всех видеороликов, которые попадут в сеть. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 9.\n\nВзаиморасположение и вектора скоростей Мэда, машин и колонн в начальный момент времени, соответствующие первому тестовому примеру, продемонстрированы на рисунке.\n\nВ первом тестовом примере хронометраж видеороликов, снятых в машинах, равен соответственно .\n\nВо втором тестовом примере — .\n\nВ третьем тестовом примере — . \n\n"},{"iden":"входные данные","content":"В первой строке задано время движения Мэда T (1 ≤ T ≤ 106), ширина колонн W (1 ≤ W ≤ 106), Y-координата дороги Cy (1 ≤ Cy ≤ 106) и скорость машин Cv ( - 106 ≤ Cv ≤ 106).Во второй строке задано количество колонн N (1 ≤ N ≤ 2000).В третьей строке заданы N чисел Si, x (0 ≤ Si, x ≤ T - W, Si, x + W < Si + 1, x) — упорядоченные по возрастанию X-координаты левых точек отрезков, соответствующих колоннам. Гарантируется, что отрезки не пересекаются и не касаются друг друга.В четвёртой строке задано количество машин K (1 ≤ K ≤ 2000).В пятой строке заданы K чисел Ci, x ( - 1012 ≤ Ci, x ≤ 1012) — упорядоченные по возрастанию X-координаты машин.Все числа во входных данных целые."},{"iden":"выходные данные","content":"Выведите суммарную длительность всех видеороликов, которые попадут в сеть. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 9."},{"iden":"примеры","content":"Входные данные10 1 2 -140 2 5 93-1 4 11Выходные данные18Входные данные5 2 3 -320 35-1 0 8 9 12Выходные данные10Входные данные8 3 2 321 53-3 0 4Выходные данные13.400000000000"},{"iden":"примечание","content":"Взаиморасположение и вектора скоростей Мэда, машин и колонн в начальный момент времени, соответствующие первому тестовому примеру, продемонстрированы на рисунке.В первом тестовом примере хронометраж видеороликов, снятых в машинах, равен соответственно .Во втором тестовом примере — .В третьем тестовом примере — . "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{R} $ be the total time of movement.  \nLet $ W \\in \\mathbb{R} $ be the width of each column.  \nLet $ C_y \\in \\mathbb{R} $ be the $ y $-coordinate of the road.  \nLet $ C_v \\in \\mathbb{R} $ be the constant velocity of each car.  \n\nLet $ N \\in \\mathbb{Z}^+ $ be the number of columns.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be the ordered sequence of left $ x $-coordinates of columns, with each column occupying the interval $ [s_i, s_i + W] $ on the $ x $-axis.  \n\nLet $ K \\in \\mathbb{Z}^+ $ be the number of cars.  \nLet $ C = (c_1, c_2, \\dots, c_K) $ be the ordered sequence of initial $ x $-coordinates of cars.  \n\nMad starts at $ (0, -1) $ at time $ t = 0 $ and moves with velocity $ (1, 0) $, so his position at time $ t \\in [0, T] $ is $ (t, -1) $.  \nEach car $ i $ starts at $ (c_i, C_y) $ at time $ t = 0 $ and moves with velocity $ (C_v, 0) $, so its position at time $ t $ is $ (c_i + C_v t, C_y) $.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 10^6 $  \n2. $ 1 \\le W \\le 10^6 $  \n3. $ 1 \\le C_y \\le 10^6 $  \n4. $ -10^6 \\le C_v \\le 10^6 $  \n5. $ 1 \\le N \\le 2000 $, $ 0 \\le s_i \\le T - W $, $ s_i + W < s_{i+1} $  \n6. $ 1 \\le K \\le 2000 $, $ -10^{12} \\le c_i \\le 10^{12} $, $ c_i < c_{i+1} $  \n\n**Objective**  \nFor each car $ i \\in \\{1, \\dots, K\\} $, define the set of times $ t \\in [0, T] $ such that the line segment connecting Mad’s position $ (t, -1) $ and the car’s position $ (c_i + C_v t, C_y) $ does not intersect the interior of any column $ [s_j, s_j + W] \\times \\{0\\} $.  \n\nThe total recording time is the sum over all cars of the Lebesgue measure (total length) of the set of times $ t \\in [0, T] $ for which the line segment between $ (t, -1) $ and $ (c_i + C_v t, C_y) $ is unobstructed by any column.  \n\nCompute:  \n$$\n\\sum_{i=1}^{K} \\mu\\left( \\left\\{ t \\in [0, T] \\mid \\text{segment } \\overline{(t, -1), (c_i + C_v t, C_y)} \\cap \\bigcup_{j=1}^{N} [s_j, s_j + W] \\times \\{0\\} = \\emptyset \\right\\} \\right)\n$$","simple_statement":"Mad walks along the line y = -1 from x = 0 to x = T at speed 1.  \nThere are N opaque columns on the x-axis, each of width W, placed at given positions without overlapping.  \nK cars move along the line y = Cy at speed Cv. Each car starts at a given x-position.  \nA car can film Mad if a straight line between Mad and the car doesn’t touch any column.  \nFind the total time during which at least one car can film Mad.","has_page_source":false}