Задача

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

Имя входного файла:	birds. in
Имя выходного файла:	birds. out
Ограничение по времени:	3 секунды
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

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

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

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

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

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

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

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

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

Примеры

birds. in	birds. out
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. Хитрый министр

Имя входного файла:	roads. in
Имя выходного файла:	roads. out
Ограничение по времени:	4 секунды
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

В стране Мини-Ярославии расположено N городов. Между некоторыми городами построены дороги, причем дороги бывают грунтовые и каменные. Дополнительно выполнены следующие условия:

·  из каждого города можно попасть в любой другой, пользуясь только каменными дорогами;

·  количество каменных дорог ровно N–1;

·  между любыми двумя городами не более одной дороги;

·  нет дорог, идущих из города в него же.

К сожалению, на содержание каждой дороги в год из бюджета требуется некоторая сумма (для каждой дороги своя). Король Мини-Ярославии решил провести дорожную реформу, и оставить минимальное количество дорог так, чтобы по-прежнему можно было попасть из любого города в любой другой и так, чтобы на содержание этих дорог требовалось наименьшее число денег.

Хитрый министр дорожного конного транспорта решил подтасовать информацию о стоимостях содержания дорог так, чтобы король принял решение оставить именно каменные дороги. Если обман вскроется, министра ждет страшное наказание, поэтому для себя министр решил следующее:

·  чем больше подтасовка — тем больше вероятность попасться, поэтому, если стоимостью подтасовки конкретной дороги назвать модуль разности между «подтасованной» стоимостью ее содержания и реальной, то министр хочет, чтобы сумма стоимостей подтасовки для всех дорог была минимальной;

·  стоимость содержания каменных дорог по подтасованному документу должны быть не больше, чем стоимость содержания любого другого набора дорог, соединяющего все города (если у двух наборов стоимости содержания дорог равны, то министру удастся убедить короля сохранить именно каменные дороги).

Напишите программу, которая вычислит, как надо подтасовать стоимости дорог, чтобы министр мог достичь поставленной цели.

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

Входной файл содержит сначала число N (2 ≤ N ≤ 50) — количество городов, затем число M — количество дорог. Далее в файле задано M троек чисел, описывающих дороги, причем первые N–1 дорог — каменные, а остальные — грунтовые. Каждая дорога задается номерами городов, которые она соединяет (по каждой дороге можно ездить как в одну, так и в другую сторону), а также стоимостью ее содержания в год. Стоимость содержания — положительное целое число, не превышающее 1000.

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

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

Примеры

roads. in	roads. out
4 5 4 1 7 2 1 5 3 4 4 4 2 5 1 3 1	4 5 4 1 4 2 1 5 3 4 4 4 2 5 1 3 4

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

Имя входного файла:	rhombs. in
Имя выходного файла:	rhombs. out
Ограничение по времени:	400 миллисекунд
Ограничение по памяти:	32 мегабайта
Максимальный балл:	100 баллов

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

Два соседних треугольника образуют ромб. Существует 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 в некотором разбиении исходного многоугольника.

Примеры

rhombs. in	rhombs. out
6 1 2 2 2 3 2 4 2 5 2 6 2	4 4 4