Третий контест окончен.

Поздравляем уже традиционно успешно выступающих Рената Баширова, Никиту Ключникова и Георгия Чебанова! Спасибо всем, кто принял участие в третьем контесте!

Задачи контеста:

Во всех задачах ограничения по памяти - 64 мегабайта, по времени - 3 секунды.

Задача A. Орлы и дятлы

В лесу находятся гнезда орлов и дятлов. Когда у орлов вылупились птенцы, они решили огородить «детскую площадку», на которой молодежь могла бы резвиться под надзором взрослых особей. Орлы хотят, чтобы детская площадка имела максимально возможную площадь, и чтобы дополнительно выполнялись следующие условия:

• площадка являлась выпуклым многоугольником, в вершинах которого находились гнезда орлов;
• зная привычку дятлов все время долбить и опасаясь, что какой-нибудь дятел насмерть задолбает кого-нибудь из еще неокрепших птенцов, орлы хотят, чтобы на территории площадки (а также на ее границе) не было гнезд дятлов.

Напишите программу, которая по заданному расположению гнезд орлов и дятлов находит оптимальное место для строительства детской площадки.

Формат входных данных

Входной файл содержит сначала число N (3 ≤ N ≤ 100) — количество орлов, затем N пар чисел, задающих координаты гнезд орлов, затем число M (0 ≤ M ≤ 100) — количество дятлов, и, наконец, M пар чисел, задающих координаты гнезд дятлов. Координаты каждого гнезда задаются парой целых чисел, каждое из которых по модулю не превышает 10000. Никакие два гнезда не находятся в одной точке.

Формат выходных данных

В выходной файл выведите сначала число K — количество гнезд орлов, которые будут вершинами многоугольника, задающего детскую площадку, а затем K чисел — номера гнезд орлов, которые будут вершинами этого многоугольника (гнезда нумеруются начиная с 1 в порядке, в котором они заданы во входном файле). Гнезда должны быть перечислены в порядке обхода вершин многоугольника по или против часовой стрелки. Если построить площадку ненулевой площади не удастся, в выходной файл выведите одно число 0.

Примеры

stdin	stdout
3 0 0 3 0 0 4 1 1 1	0
4 0 0 3 0 3 3 0 3 1 1 1	3 4 2 3

Задача B. Ромбы

Рассмотрим плоскость, на которой задана треугольная решетка, состоящая из одинаковых треугольников так, как показано на рисунке:

Два соседних треугольника образуют ромб. Существует 3 типа ромбов:

Будем рассматривать многоугольники со сторонами, идущими по сторонам сетки. Будем называть многоугольник ромбическим, если его можно разбить на непересекающиеся ромбы типа A, B и C. Для примера рассмотрим следующий шестиугольник. Его можно разбить на 4 ромба типа A, 4 ромба типа B и 4 ромба типа C:

Для данного ромбического многоугольника вычислите количество ромбов каждого из типов A, B и C в некотором его разбиении.

Формат входных данных

Первая строка входного файла содержит целое число n (3 ≤ n ≤ 50000) — число сторон ромбического многоугольника. Каждая из последующих n строк содержит описание одной стороны многоугольника. Стороны даны в порядке обхода многоугольника в направлении часовой стрелки. Никакие две последовательные стороны многоугольника не лежат на одной прямой. Описание каждой стороны состоит из двух целых чисел d и k. Число d задает направление стороны согласно следующему рисунку:

Число k задает длину стороны многоугольника, выраженную в числе сторон треугольников сетки. Сумма всех k не превышает 100000.

Формат выходных данных

Первая и единственная строка выходного файла должна содержать три числа, разделенных одним пробелом, задающих соответственно число ромбов типа A, B и C в некотором разбиении исходного многоугольника.

Примеры

stdin	stdout
6 1 2 2 2 3 2 4 2 5 2 6 2	4 4 4

Задача C. Ломаная

На плоскости дана ломаная, каждое из звеньев которой перпендикулярно биссектрисе одного из углов, образованных координатными осями. Никакая вершина ломаной не лежит на звене ломаной. В частности, никакие две вершины ломаной не совпадают. Ваша задача — подсчитать число точек самопересечения ломаной.

Формат входных данных

В первой строке входного файла записано N — количество вершин ломаной (2≤ N ≤ 100000). В последующих N строках записаны координаты вершин — целые числа, по модулю не превосходящие 1000000. Вершины перечислены в порядке прохода по ломаной.

Формат выходных данных

В первой строке выходного файла выведите число точек самопересечения ломаной.

Примеры

stdin	stdout
8 1 0 3 2 5 0 4 -1 1 2 3 4 5 2 2 –1	3

Задача D. Гора

Недавно археологи нашли древнюю рукопись. В ней автор описывает свои похождения по горе Х загадочного материка Атлантида.

Известно, что гора имеет высоту H метров и длину L метров. Если расположить чертеж профиля горы на координатной плоскости так, что гора будет расположена в первой координатной четверти, ее самая левая точка будет иметь координаты (0, 0), а правая – (L, 0), то профиль горы будет иметь вид ломаной такого вида, что:

• все вершины ломанной имеют целочисленные абсциссы и ординаты;
• каждое звено ломаной либо параллельно оси абсцисс, либо наклонено к ней под углом 45 градусов;
• существует хотя бы одна вершина ломаной с ординатой равной H и не существует вершин с ординатой больше H;
• ломаная имеет с осью абсцисс только две общие точки – (0, 0) и (L, 0);
• на ломаной лежит ровно L+1 целочисленная точка.

В рукописи указываются замеры – последовательность высот, в порядке прохождения горы слева направо. Известно, что замеры делались только в целочисленных точках. Расстояние между любыми двумя соседними замерами не менее 1 метра.

Так как, возможно, автор делал замеры не в каждой целочисленной точке, то однозначно восстановить профиль горы по записям в рукописи в общем случае невозможно.

Ваша задача найти количество возможных различных профилей горы, соответствующих найденной рукописи.

Формат входных данных

В первой строке записана тройка чисел H, L, K (1 ≤ H, L ≤ 40, 0 ≤ K ≤ L+1), где H – высота горы, L – длина горы, K – количество замеров. Во второй строке записано K целых чисел, каждое из которых соответствует высоте замера. Порядок соответствует движению слева направо.

Формат выходных данных

Выведите количество возможных различных профилей горы, соответствующих найденной рукописи.

Примеры

stdin	stdout
2 5 0	3
3 8 4 2 2 3 1	7
40 40 0	0

Задача E. Монеты

Одна маленькая девочка очень любит раскладывать на столе монеты. У нее имеется N монет и один медальон, все круглой формы. Девочка положила на стол медальон, а вокруг него монеты, чтобы получилась "ромашка" - все монеты образовали замкнутое кольцо вокруг медальона. При этом каждая монета касается только медальона и соседних двух монет, как показано на рисунке ниже.

Монеты, расположенные последовательно по часовой стрелке, имеют радиусы r1, ..., rN. Девочке известны радиусы монет, но, к сожалению, она не знает радиус своего медальона, и очень хотела бы его рассчитать. Помогите девочке справиться с этой задачей.

Формат входных данных

Первая строка содержит число N (3 ≤ N ≤ 100) — количество монет. Вторая строка содержит радиусы каждой монеты, разделенные одним или несколькими пробелами. Радиусы задаются с точностью до двух знаков после десятичной точки.

Формат выходных данных

Выведите радиус медальона, с точностью до двух знаков после десятичной точки.

Примеры

stdin	stdout
4 2 2 2 2	0.83