Скоро новый год и Санта-Клаус уже начал готовить свою волшебную оленью упряжку, на которой он развозит подарки детям. Известно, что упряжку везут несколько волшебных оленей, на каждом из которых едут два эльфа.
Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо \( b_j \lt a_i \lt b_k \), либо \( b_k \lt a_i \lt b_j\).
Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.
Помогите Санте выяснить, какое максимальное количество оленей он сможет включить в упряжку, каких оленей ему следует выбрать, и какие эльфы должны на них ехать.
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно \( (1 \le m, n \le 100 000) \).
Вторая строка содержит m целых чисел ai – строптивость оленей \( (0 \le a_i \le 10^9) \). В третьей строке записаны \(n\) целых чисел \(b_i\) – темперамент эльфов \( (0 \le b_i \le 10^9) \).
В первой строке выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.
И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.
4 6 2 3 4 5 1 3 2 2 5 2
2 1 1 2 2 4 5
Одной из первоочередных задач, стоящих перед министерством обороны Флатландии, является модернизация вооружения. В связи с этим было решено построить новый испытательный полигон.
По форме полигон представляет собой выпуклый многоугольник. Для демонстрации военных испытаний на полигоне различным чиновникам, неподалеку от него решено было построить наблюдательный центр. В результате длительных исследований было установлено, что основной характеристикой местоположения наблюдательного центра является степень этого центра относительно полигона.
Степень точки A относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке A, имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки A до некоторой точки многоугольника: dmin и dmax. Степенью точки относительно данного многоугольника назовем минимум величины dmin×dmax по всем таким лучам.
Военные не справляются с задачей вычисления степени наблюдательного центра относительно полигона и решили подключить к этой задаче вас. Помогите им!
Будем считать, что наблюдательный центр находится в точке (0, 0). На вход программы поступает описание полигона.
В первой строке вводится число n – количество вершин полигона ( 3
n100). Следующие n строк содержат по два вещественных числа – координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают 1000 по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.
Выведите одно число – степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на 10-4.
3 1.0 2.0 3.0 2.0 0.5 3.25
7.0000000000