Задача A. Выпуклая оболочка ≡

Условие

Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению множество, содержащее заданное множество точек X, называется выпуклой оболочкой множества X.

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.

Формат входного файла

Первая строка входного файла содержит число n — количество углов. Каждая из следующих n строк описывает углы. Каждый угол описывается координатами трех точек: вершины и двух отличных от вершины точек — по одной на каждом из лучей.

Формат выходного файла

Выведите в выходной файл границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходном файле не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все числа в выходном файле должны быть целыми и не превосходить 10⁵ по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа.

На первой строке выведите l — количество объектов в ответе. Следующие l строк должны со- держать описание объектов. Объекты описываются следующим образом:

• Отрезок: "segment x₁ y₁ x₂ y₂", где (x₁, y₁) и (x₂, y₂) — концы отрезка, отрезок считается направленным от (x₁, y₁) к (x₂, y₂).
• Луч, направленный от начала: "outray x₁ y₁ x₂ y₂", где (x₁, y₁) — начало луча, а (x₂, y₂) — произвольная точка на луче, отличная от начала.
• Луч, направленный к началу: "inray x₁ y₁ x₂ y₂", где (x₂, y₂) — начало луча, а (x₁, y₁) — произвольная точка на луче, отличная от начала.
• Прямая: "line x₁ y₁ x₂ y₂", где (x₁, y₁) и (x₂, y₂) — две точки на прямой, причем при движении вдоль прямой в ее направлении точка (x₁, y₁) следует ранее точки (x₂, y₂).

Если выпуклой оболочкой является вся плоскость, то выведите l = 0.

Ограничения

1 ≤ n ≤ 1000

Все координаты целые и не превышают 10⁴ по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

Примеры тестов

2
3 1 4 1 4 4
2 2 4 3 3 4

3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5

2
0 0 1 0 0 1
0 0 -1 0 0 1

1
line 1 0 -1 0

2
0 0 1 0 0 1
0 0 -1 0 0 -1

0

Задача B. Гражданская оборона ≡

Условие

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

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

Формат входного файла

Первая строка входного файла содержит число n — количество селений. Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения.

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

Формат выходного файла

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100 000

Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Примеры тестов

4
1 2 6 10
2
7 3

2 2 1 1

Задача C. Клетка для хомячка ≡

Условие

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

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

Теперь Андрюша хочет положить эти две фигуры на стол так, чтобы получилась клетка для хомячка. Фигуры должны быть положены таким образом, чтобы каждый кубик касался стола гранью. Стороны нижних граней кубиков должны быть параллельны сторонам стола. Любые два кубика, принадлежащие различным фигурам, должны либо не касаться друг друга, либо иметь общую грань, либо иметь общее ребро. Фигуры разрешается поворачивать и переворачивать.

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

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

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

Формат входного файла

Первая строка входного файла содержит два числа: h₁ и w₁. Следующие h₁ строк содержат по w₁ символов и описывают первую фигуру, вид сверху. Каждый из этих символов — либо "*" (звездочка), либо "." (точка), звездочка обозначает кубик, а точка — пустое место. Следующая строка содержит два числа: h₂ и w₂. Следующие h₂ строк содержат по w₂ символов и описывают вторую фигуру в формате, аналогичном первой. Каждая из фигур связна и содержит хотя бы один кубик.

Формат выходного файла

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

Ограничения

1 ≤ h₁, w₁, h₂, w₂ ≤ 10

Примеры тестов

8 8
........
.***....
..**....
.*****..
...*.*..
...***..
****....
........
8 8
........
........
........
........
*******.
........
........
........

4

Задача D. Пузырьки 1D ≡

Условие

Сережа — большой любитель игр на сотовом телефоне. Недавно он скачал из интернета новую игру "Пузырьки 1D". Опишем правила игры.

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

За один ход разрешается выбрать любую группу, состоящую хотя бы из двух пузырьков, и взорвать ее. За взрыв группы, содержащей k пузырьков, игрок получает k² очков. После взрыва группы пузырьки, которые находились сверху, опускаются вниз.

Например, ниже на рисунке показана позиция, содержащая 10 пузырьков. В ней четыре группы, содержащие 3, 2, 4 и 1 пузырек, соответственно. Если взорвать группу, содержащую четыре пузырь- ка, то игрок получит 16 очков, и верхние 5 пузырьков опустятся вниз. В получившейся позиции 6 пузырьков, и две группы по 3 пузырька в каждой.

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

Формат входного файла

Входной файл содержит одну строку, состоящую из букв "R", "G", "B" и "Y", описывающую начальную позицию. Буквы задают цвета пузырьков в порядке просмотра сверху вниз ("R" означает красный пузырек, "G" — зеленый, "B" — синий, а "Y" — желтый).

Формат выходного файла

Выведите в выходной файл одно число — максимальное количество очков, которое сможет заработать Сережа. Если уничтожить все пузырьки невозможно, выведите 0.

В первом примере следует действовать следующим образом: сначала надо взорвать группу из четырех красных пузырьков, получив 16 очков. Затем надо взорвать в любом порядке получившиеся две группы по 3 пузырька, получив по 9 очков за каждую.

Ограничения

В заданной позиции не менее двух и не более 100 пузырьков.

Примеры тестов

RRRGGRRRRG

34

RB

0

Задача E. Справедливая последовательность ≡

Условие

Последовательность из нулей и единиц четной длины назовем справедливой, если на четных местах этой последовательности столько же единиц, сколько на нечетных. Например, последовательность "011011" является справедливой, а последовательность "011101" — нет.

Задана некоторая последовательность нечетной длины из нулей и единиц. Из нее разрешается удалить одну цифру. Какую цифру следует удалить, чтобы последовательность стала справедливой?

Например, из последовательности "0111011" с этой целью можно удалить вторую цифру.

Формат входного файла

Входной файл содержит одну строку. Эта строка содержит последовательность нечетной длины из нулей и единиц.

Формат выходного файла

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

Ограничения

Длина последовательности не превышает 200 001.

Примеры тестов

0111011

2