Горнолыжник, готовясь к соревнованиям, нарисовал на бумаге схему горнолыжной трассы для выбора оптимального маршрута спуска. На схеме расположенные на трассе ворота представлены горизонтальными отрезками. Никакая пара ворот не имеет общих точек.
Маршрут должен представлять собой ломаную, начинающуюся в точке старта на вершине горы и заканчивающуюся в точке финиша у ее подножия. Маршрут выбирается таким образом, что y-координата каждой следующей вершины ломаной оказывается строго меньше y-координаты предыдущей вершины. Один из возможных маршрутов представлен на рисунке.
За каждые ворота, через которые не проходит маршрут, лыжнику начисляются штрафные очки. Общий штраф за спуск по маршруту вычисляется как сумма длины маршрута и штрафных очков за непройденные ворота.
Требуется написать программу, которая определяет, какой минимальный общий штраф горнолыжник может получить при прохождении трассы.
В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.
В выходной файл выведите наименьший возможный общий штраф за прохождение трассы с точностью не менее 4 знаков после десятичной точки.
Потестовая.
4 3 6 3 1 5 7 4 1 4 5 5 10 1 2 4 5 2 5 2 0
7.8126
Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.
Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.
Напишите программу, которая определит, есть ли у мухи шанс спастись, и если есть, то выведет, что должна муха для этого делать.
Во входном файле заданы числа V, W, A, T, C, D. Все числа целые. 0≤V≤W≤1000, 0≤A≤1000, 0<T≤1000, –1000000≤C≤D≤1000000.
Если муха может спастись, выведите, как она должна для этого лететь. Для этого выведите последовательность команд для мухи. Количество команд не должно превышать 100. Каждая команда задается двумя числами Ti, Ai, которые обозначают, что в течение времени Ti муха должна лететь с ускорением Ai. Ti и Ai не обязаны быть целыми, Ti должны быть положительны (не могут быть равны 0), сумма всех Ti должна быть равна T с точностью до 10-6.
Если, в рамках указанных ограничений, муха спастись не сможет, в выходной файл выведите одно число –1 (минус 1).
Примечания
Муха может сначала снизить скорость до 0, а затем полететь в обратную сторону (см. примеры).
Если в момент времени T муха окажется на концах отрезка, т.е. в точке C или D, она все равно погибнет.
Комментарии к примерам тестов
1. Муха не сможет спастись.
2. Сначала в течение времени 0.2 муха летит с постоянной скоростью 10, а затем ускоряется с ускорением 4
3. Муха сначала тормозит с ускорением -5, а затем с этим же ускорением начинает лететь в обратную сторону. Набрав скорость 10, муха продолжает лететь с ней без ускорения.
10 10 5 1 -100 100
-1
10 20 5 1 9 11
1 5
10 10 5 5 0 1000
4.000000000000000000 -5 1.000000000000000000 0
На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>
В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.
1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.
В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).
Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).
Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).
3 0 1 0 0 1 1 0 1 2
1 0 0
5 0 2 0 2 4 1 1 3 2 1 3 -1 1 3 -2
3 -1 -5
3 0 1 0 1 2 1 -2 -1 2
No solution
Власти Флатландии решили построить новый мост через реку Нижний Флат, протекающую с юга на север через территорию страны. В связи с финансовым кризисом средства строителей существенно ограничены, поэтому решено было построить мост минимальной возможной длины. 
Введем координатную систему таким образом, чтобы ось OY была направлена с юга на север, а ось OX с запада на восток. Берега реки представляют собой ломаные, бесконечные в обе стороны. Левый берег начинается лучом, направленным на юг из точки (x1,1,y1,1), продолжается отрезками (x1,1,y1,1) − (x1,2,y1,2), (x1,2,y1,2)− (x1,3,y1,3), ..., (x1,m−1,y1,m−1) − (x1,m,y1,m) и заканчивается лучом, направленным на север из точки (x1,m,y,m).
Аналогично, правый берег реки начинается лучом, направленным на юг из точки (x2,1,y2,1), продолжается отрезками (x2,1,y2,1) − (x2,2,y2,2), (x2,2,y2,2) − (x2,3,y2,3), ..., (x2,n−1,y2,n−1) − (x2,n,y2,n) и заканчивается лучом, направленным на север из точки (x2,n,y2).
Помогите руководству Флатландии выяснить, мост какой минимальной длины можно построить.
Первая строка входного файла содержит целое число m (2 ≤ m ≤ 100). Следующие m строк содержат по два целых числа координаты вершин ломаной левого берега: x1,1, y1,1, x1,2,y1,2, ...,x1,m, y1,m.
Следующая строка входного файла содержит целое число n (2 ≤ n ≤ 100). Следующие n строк содержат по два целых числа координаты вершин ломаной правого берега: x2,1, y2,1, x2,2, y2,2, ..., x2,n, y2,n.
Известно, что x1,1 < x2,1, каждая из ломаных не имеет самопересечений и самокасаний, ломаные не имеют общих точек. Все отрезки каждой из ломаных имеют положительную длину. Все координаты не превосходят 104 по абсолютной величине
Выведите в выходной файл одно вещественное число: минимальную возможную длину моста. Ваш ответ будет проверяться с точностью 10−5.
Оптимальное положение моста показано на следующем рисунке:
4 6 1 3 1 3 0 0 3 3 9 3 2 3 6 5
1.4142135623730951