В городе, являющемся одним из ведущих Российских образовательных центров, решили построить пивную. Естественно, что ректоры находящихся в городе ВУЗов потребовали, чтобы пивная была максимально удалена от каждого из ВУЗов. Помогите директору будущей пивной выбрать оптимальное место для строительства. Граница города представляет собой выпуклый многоугольник. Положение ВУЗов задается координатами точек внутри этого многоугольника. Пивную нужно построить так, чтобы расстояние от нее до ближайшего вуза было максимально. Пивную можно строить как внутри города, так и на его границе.

Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение. Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно, что привидения не отражаются в зеркале! А кубики отражаются. Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие — всего лишь отражение в зеркале. Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.

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

Адам, будучи организованным человеком, всегда любит порядок. Иногда он любит вспоминать, как когда-то проводил долгие часы за компьютером, перенося данные на диски.

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

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

1 ≤ T ≤ 100. 1 ≤ X ≤ 700. 1 ≤ S _i ≤ X .

В задаче есть две группы тестов: 1. 1 ≤ N ≤ 10 - оценивается в 40 баллов 2. 1 ≤ N ≤ 1 ⁴ - оценивается в 60 баллов

Флатландский валун имеет форму многоугольника (не обязатеьно выпуклого). Для простоты будем рассматривать только многоугольники, у которых любые 3 вершины не лежат на одной прямой. Такие валуны получаются из разных видов камней, необязательно однородной плотности. Тем не менее, вы знаете расположение его центра тяжести. Сейчас мы положили на горизонтальную прямую две вершины камня (назовём их базовыми), и отпустили. В случае, если центр тяжести находится над отрезком, соединяющим базовые вершины, или над базовыми вершинами, то валун будет стоять. Иначе сила тяжести заставит его катится в определённом направлении.

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

Иначе он продолжит вращаться, пока в конце концов не остановится, так как во Флатляндии вечный двигатель невозможен. Движение валуна происходит в вязкой среде, то есть инерция отсутствует, и валун остановится, как только сила тяжести позволит ему. Зная координаты вершин валуна и его центра тяжести, вычислите количество поворотов, которые совершит валун перед остановкой.