Эхсан обожает геометрию! Больше всего ему нравится вращать точки!

Если дана точка на плоскости, Эхсан любит вращать её на k градусов (против часовой стрелки) вокруг начала координат. Каков результат такого вращения?

После войны сверхзвуковая ракета стала самым популярным видом общественным транспортом.

Каждая сверхзвуковая ракета состоит из двух «двигателей». Каждый двигатель представляет собой множество из «источников питания». Первый двигатель состоит из \(n\) источников питания, а второй из \(m\). Источник питания можно представить как точку \((x_i, y_i)\) на 2-D плоскости. Все точки в каждом двигателе различные.

Вы можете влиять на каждый двигатель отдельно. Есть два действия, которые вы можете делать с каждым двигателем. Вы можете делать каждое действие столько раз, сколько хотите.

1. Каждый источник питания двигателя \((x_i, y_i)\) станет \((x_i+a, y_i+b)\), где \(a\) и \(b\) могут быть любыми действительными числами. Другими словами, все источники питания будут смещены.
2. Каждый источник питания двигателя \((x_i, y_i)\) станет \((x_i \cos \theta - y_i \sin \theta, x_i \sin \theta + y_i \cos \theta)\), где \(\theta\) может быть любым действительным числом. Другими словами, все источники питания будут повернуты.

Двигатель работает следующим способом: после того, как оба двигателя будут заряжены, их источники питания объединяются вместе (координаты источников питания разных двигателей могут совпадать). А именно, если есть две точки питания \(A(x_a, y_a)\) и \(B(x_b, y_b)\), то для каждого действительного числа \(k\), такого что \(0 \lt k \lt 1\), будет сгенерирован новый источник питания \(C_k(kx_a+(1-k)x_b,ky_a+(1-k)y_b)\). Эта процедура будет повторена еще раз со всеми новыми и старыми источниками. После этого будет сгенерировано «силовое поле» из всех источников питания.

Сверхзвуковая ракета будет «безопасна» тогда и только тогда, когда после всех ваших действий на генераторы, уничтожение любого источника питания не изменит силовое поле (в сравнении со случаем, когда ни один источник питания не был уничтожен). Два силовые поля считаются одинаковыми тогда и только тогда, когда каждый источник питания в одном силовом поле принадлежит и второму.

У вас есть сверхзвуковая ракета, проверьте безопасна ли она.

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

Вам даны \(n\) точек на плоскости. Никакие две из них не совпадают, никакие три не лежат на одной прямой.

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

У Васи есть кукурузное поле, описываемое двумя числами — \(n\) и \(d\). Кукурузное поле можно представить в декартовой системе координат как прямоугольник с углами в точках \((0, d), (d, 0), (n, n - d)\) и \((n - d, n)\).

Пример кукурузного поля при \(n = 7\) и \(d = 2\).

Также Вася знает координаты \(m\) кузнечиков. Кузнечик номер \(i\) находится в точке \((x_i, y_i)\). Так как Вася не любит, когда кузнечики поедают его кукурузу, то про каждого кузнечика Вася хочет знать, находится ли он на поле или нет. Считается, что кузнечик находится на кукурузном поле, если он находится внутри или на границах прямоугольника, описанного выше.

Помогите Васе! Сообщите про каждого кузнечика, находится ли он на кукурузном поле.

В этой задаче мы рассматриваем упрощённую модель города Барселона.

Барселона может быть представлена как плоскость, а её улицы — как прямые вида \(x = c\) и \(y = c\) для любого целого числа \(c\) (то есть, улицы представляют собой прямоугольную сетку). Однако есть кое-что, что отличает Барселону от Манхеттена, а именно, проспект, который называется Avinguda Diagonal (Диагональный проспект) и который может быть представлен на плоскости как множество точек \((x, y)\), удовлетворяющих \(ax + by + c = 0\).

Перемещаться по городу можно только по улицам, в том числе и по Диагональному проспекту. Вам даны точки \(A\) и \(B\) в Барселоне. Найдите минимальное расстояние, которое необходимо пройти, чтобы попасть в точку \(B\) из точки \(A\).

Есть \(n\) точек на плоскости. Многоугольник, сформированный этими \(n\) точками, строго выпуклый, то есть многоугольник выпуклый и нет трех коллинеарных точек (то есть лежащих на одной прямой). Точки пронумерованы от \(1\) до \(n\) по часовой стрелке.

Определим расстояние между двумя точками \(p_1 = (x_1, y_1)\) и \(p_2 = (x_2, y_2)\) как их манхэттенское расстояние: \(\)d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.\(\)

Более того, определим периметр многоугольника как сумму манхэттенских расстояний между всеми соседними парами точек на нем; если точки на многоугольнике упорядочены как \(p_1, p_2, \ldots, p_k\) \((k \geq 3)\), тогда периметр многоугольника равен \(d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)\).

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

Обратите внимание, что при проверке многоугольника на самопересечение, ребра многоугольника рисуются как прямые линии. Например, на следующих рисунках:

В многоугольнике, который изображен посередине, последовательность точек (\(p_1, p_3, p_2, p_4\)) неправильная потому, что многоугольник самопересекается. Правый многоугольник (ребра которого напоминают Манхэттенское расстояние) имеет такую же последовательность и не самопересекается, но мы рассматриваем ребра как прямые отрезки. Правильный способ нарисовать этот многоугольник — это использовать последовательность (\(p_1, p_2, p_3, p_4\)), пример которого можно увидеть на левом рисунке.

Вычислите \(f(3), f(4), \ldots, f(n)\). Другими словами, найдите максимально возможный периметр для каждого количества точек (то есть от \(3\) до \(n\)).

Ани и Борна играют в короткую игру на многочлене двух переменных. Многочлен имеет специальный вид: одночлены без коэффициентов фиксированы, а на месте всех коэффициентов есть пропуски, которые нужно заполнить, например \(\) \_ xy + \_ x^4 y^7 + \_ x^8 y^3 + \ldots \(\)

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

Ани вредная, поэтому она хочет, чтобы многочлен был неограничен. Кроме сердца Борны, она также может украсть части многочлена. Однако, Ани лишь чуть-чуть воришка, поэтому она может украсть не более одного одночлена перед тем, как Борна заполнит пропуски.

Если Ани и Борна сделают оптимально свой единственный ход, то кто выиграет?

Даны \(n\) точек на плоскости, \((x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)\).

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

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

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

Поскольку планеты достаточно удалены друг от друга, их можно считать точками в евклидовом трехмерном пространстве. Расстояние между точками (x_i, y_i, z_i) и (x_j, y_j, z_j) вычисляется по формуле . Спасательная база может располагаться в любой точке пространства, в том числе, совпадать с какой либо из планет.

Галактика в опасности! Спасите космических спасателей и укажите им искомую точку.

У Маши есть три палочки длиной \(a\), \(b\) и \(c\) сантиметров. За одну минуту Маша может увеличить длину любой из палочек на один сантиметр. Ломать палочки не разрешается.

За какое минимальное время Маша сможет собрать треугольник положительной площади, сторонами которого будут палочки, если концы палочек должны быть вершинами треугольника?

Once upon a time Algoland and Berland were a single country, but those times are long gone. Now they are two different countries, but their cities are scattered on a common territory.

All cities are represented as points on the Cartesian plane. Algoland consists of \(a\) cities numbered from \(1\) to \(a\). The coordinates of the \(i\)-th Algoland city are a pair of integer numbers \((xa_i, ya_i)\). Similarly, Berland consists of \(b\) cities numbered from \(1\) to \(b\). The coordinates of the \(j\)-th Berland city are a pair of integer numbers \((xb_j, yb_j)\). No three of the \(a+b\) mentioned cities lie on a single straight line.

As the first step to unite the countries, Berland decided to build several bidirectional freeways. Each freeway is going to be a line segment that starts in a Berland city and ends in an Algoland city. Freeways can't intersect with each other at any point except freeway's start or end. Moreover, the freeways have to connect all \(a+b\) cities. Here, connectivity means that one can get from any of the specified \(a+b\) cities to any other of the \(a+b\) cities using freeways. Note that all freeways are bidirectional, which means that one can drive on each of them in both directions.

Mayor of each of the \(b\) Berland cities allocated a budget to build the freeways that start from this city. Thus, you are given the numbers \(r_1, r_2, \dots, r_b\), where \(r_j\) is the number of freeways that are going to start in the \(j\)-th Berland city. The total allocated budget is very tight and only covers building the minimal necessary set of freeways. In other words, \(r_1+r_2+\dots+r_b=a+b-1\).

Help Berland to build the freeways so that:

• each freeway is a line segment connecting a Berland city and an Algoland city,
• no freeways intersect with each other except for the freeway's start or end,
• freeways connect all \(a+b\) cities (all freeways are bidirectional),
• there are \(r_j\) freeways that start from the \(j\)-th Berland city.

Орехус застрял в плоском мире. Чтобы выбраться, необходимо решить следующую задачу.

Вам даны \(n\) прямоугольников с вершинами в точках \((0, 0)\), \((x_i, 0)\), \((x_i, y_i)\), \((0, y_i)\). Также для каждого прямоугольника вам дано число \(a_i\). Необходимо выбрать некоторые из них, чтобы площадь их объединения минус сумма их \(a_i\) была максимальна.

Гарантируется, что нет вложенных прямоугольников.

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

NN  — заядлый интернет-пользователь, поэтому он очень много времени проводит в социальных сетях и различных форумах. Как-то раз ему попалась очень занятная картинка, на которой предлагалось сравнить размеры двух центральных кружков:

Оказалось, что кружки равны. NN очень удивил данный факт, поэтому он решил самостоятельно построить картинку.

Ему удалось посчитать количество внешних кругов \(n\), а так же радиус внутреннего круга \(r\). По мнению NN, исходя из этой информации можно в точности найти радиус всех внешних кругов \(R\) таким образом, чтобы внутренний кружок касался всех остальных внешним образом, а также каждая пара соседних внешних кружочков также касалась. Сколько NN ни старался угадать нужный радиус, у него так и не получилось сделать это.

Помогите NN найти необходимый радиус внешних кругов для построения картинки.

Вам дан набор из \(n\) точек на 2D-плоскости. Гарантируется, что нет трех точек на одной прямой.

Пентаграмма — это набор из \(5\) точек \(A,B,C,D,E\), которые можно расположить следующим образом. Обратите внимание, что длина отрезков не имеет значения, главное то, что пересечения существуют.

Подсчитайте количество способов выбрать \(5\) точек из данного набора, которые образуют пентаграмму.

У Васи есть \(n\) различных точек \(A_1, A_2, \ldots A_n\) на плоскости. Никакие три из них не лежат на одной прямой. Он хочет расположить их в некотором порядке \(A_{p_1}, A_{p_2}, \ldots, A_{p_n}\), где \(p_1, p_2, \ldots, p_n\) — это некоторая перестановка чисел от \(1\) до \(n\).

Сделав так, он нарисует ориентированную ломаную на этих вершинах, проведя направленные отрезки из каждой точки в следующую в выбранном порядке точку. То есть для всех \(1 \leq i \leq n-1\) он проведет направленный отрезок из точки \(A_{p_i}\) в точку \(A_{p_{i+1}}\). Он хочет, чтобы получившаяся ломаная удовлетворяла \(2\)-м условиям:

• она будет несамопересекающейся, то есть любые \(2\) отрезка, которые не являются соседними, не имеют общих точек.
• она будет извилистой.

У Васи есть строка \(s\), состоящая из \((n-2)\)-х символов "L" или "R". Будем называть направленную ломаную извилистой, если её \(i\)-й поворот будет налево, если \(s_i = \) "L" и направо, если \(s_i = \) "R". Более формально: \(i\)-й поворот ломаной будет в точке \(A_{p_{i+1}}\), в ней направленный отрезок из точки \(A_{p_i}\) в точку \(A_{p_{i+1}}\) поменяется на направленный отрезок из точки \(A_{p_{i+1}}\) в точку \(A_{p_{i+2}}\). Обозначим вектор \(\overrightarrow{v_1} = \overrightarrow{A_{p_i} A_{p_{i+1}}}\) и вектор \(\overrightarrow{v_2} = \overrightarrow{A_{p_{i+1}} A_{p_{i+2}}}\). Тогда если для того, чтобы повернуть вектор \(\overrightarrow{v_1}\) на наименьший возможный угол, чтобы его направление совпало с направлением вектора \(\overrightarrow{v_2}\) надо сделать поворот против часовой стрелки, то будем говорить, что \(i\)-й поворот налево, а иначе направо. Для лучшего понимания посмотрите картинки, на которых изображены различные варианты поворотов:

На этой картинке изображены повороты налево

На этой картинке изображены повороты направо

Вам даны координаты точек \(A_1, A_2, \ldots A_n\) на плоскости и строка \(s\). Найдите перестановку \(p_1, p_2, \ldots, p_n\) чисел от \(1\) до \(n\), такую что ломаная, которую нарисует Вася, будет удовлетворять двум заданным условиям.

Эта задача такая же как и предыдущая, но с большими ограничениями.

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

На входе на станцию висит карта, описывающая систему проводов электростанции. Селена лучше всего из друзей разбирается в математике. Он решил нарисовать карту на декартовой плоскости. Теперь каждый полюс это точка по координатам \((x_i, y_i)\). Так как все полюса различны, то различны и точки, представляющие их. Также каждые два полюса соединены друг с другом проводом, представляющим из себя бесконечную в обе стороны прямую на плоскости. В случае если более двух полюсов лежат на одной прямой, то они все соединены одним общим проводом.

Селена думает, что когда два различных электрических провода пересекаются, то между ними может возникать опасная интерференция. Поэтому он интересуется, сколько пар проводов пересекаются?

Вам задан массив \(a_1, a_2, \dots, a_n\). Вам необходимо разделить его на \(k\) подотрезков (так, что каждый элемент принадлежит ровно одному подотрезку).

Весом подотрезка \(a_l, a_{l+1}, \dots, a_r\) назовем значение \((r - l + 1) \cdot \max\limits_{l \le i \le r}(a_i)\). Весом разбиения — суммарный вес его подотрезков.

Найдите разбиение минимального веса.

Вам дан кусочек бумаги в форме простого многоугольника \(S\). Ваша задача — превратить его в простой многоугольник \(T\), у которого такая же площадь, как у \(S\).

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

Многоугольники, заданные вам, имеют целочисленные координаты, но вы можете получать части, которые имеют и нецелочисленные координаты.

Далее следует формальное описание задачи.

Фигурой \(Q=(Q_0,\dots,Q_{n-1})\) называется последовательность из трех или более точек на плоскости такая, что:

• Замкнутая ломаная \(Q_0Q_1Q_2\dots Q_{n-1}Q_0\) не имеет самокасаний и самопересечений, а поэтому образует простой многоугольник.
• Эта ломаная обходит многоугольник против часовой стрелки.

Обозначим многоугольник, ограниченный фигурой \(Q\), за \(P(Q)\).

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

Обратите внимание, что отражать фигуры запрещено. Кроме того, обратите внимание, что порядок точек важен: фигура \((Q_1,\dots,Q_{n-1},Q_0)\) не всегда эквивалентна фигуре \((Q_0,\dots,Q_{n-1})\).

На рисунке слева: фигуры \(U\) и \(V\) эквивалентны. Фигура \(W\) не эквивалентна им, потому что точки \(W\) следуют в другом порядке. Четвертая фигура не эквивалентна остальным независимо от порядка точек, потому что отражение не допускается.

Во входных и выходных данных фигура из \(n\) точек представляется как одна строка, содержащая \(2n+1\) число: число \(n\), а затем координаты точек: \(Q_{0,x}\), \(Q_{0,y}\), \(Q_{1,x}\), ...

У фигур есть идентификационные номера (ID). Данная вам фигура \(S\) имеет ID 0, фигуры, которые вы получаете в процессе решения — ID 1, 2, 3, ... в порядке, в которым вы их получаете.

Фигуры \(B_1,\dots,B_k\) образуют разделение фигуры \(A\), если:

• Объединение всех \(P(B_i)\) дает точно \(P(A)\).
• Для всех \(i\neq j\) площадь пересечения \(P(B_i)\) и \(P(B_j)\) равна нулю.

Применение ножниц уничтожает одну существующую фигуру \(A\) и создает одну или более фигуру \(B_1,\dots,B_k\), которые образуют разделение \(A\).

На рисунке фигура \(A\) (квадрат) разделена на фигуры \(B_1\), \(B_2\), \(B_3\) (три треугольника). Один из корректных способов представить одну из фигур \(B_i\) есть «3 3 1 6 1 5.1 4».

Применение скотча уничтожает одну или более существующую фигуру \(A_1,\dots,A_k\) и создает одну новую фигуру \(B\). Чтобы эта операция была выполнима, вы должны в начале указать фигуры \(C_1,\dots,C_k\), и только затем конечную фигуру \(B\). Эти фигуры должны удовлетворять следующим ограничениям:

• Для всех \(i\) фигура \(C_i\) эквивалентна фигуре \(A_i\).
• Фигуры \(C_1,\dots,C_k\) образуют разделение фигуры \(B\).

Неформально вы должны выбрать фигуру \(B\) и показать, как нужно подвинуть и повернуть все существующие \(A_i\), чтобы они заняли правильные места \(C_i\) внутри \(B\). Обратите внимание, что только фигура \(B\) получает новый ID, фигуры \(C_i\) его не получают.

Фигура называется удобным прямоугольником, если она имеет вид \(((0,0),~ (x,0),~ (x,y),~ (0,y))\) для некоторых положительных чисел \(x\) и \(y\).

Фигура называется удобным квадратом, если дополнительно \(x=y\).

Фигура \(A\) называется строго выпуклой, если все внутренние углы многоугольника \(P(A)\) меньше 180 градусов.

Подзадача 1 (5 баллов): \(S\) и \(T\) — удобные прямоугольники. Все координаты точек — целые числа от 0 до 10 включительно

Подзадача 2 (13 баллов): \(S\) — удобный прямоугольник с \(x>y\), а \(T\) — удобный квадрат

Подзадача 3 (12 баллов): \(S\) и \(T\) — удобные прямоугольники

Подзадача 4 (14 баллов): \(S\) — треугольник, а \(T\) — удобный квадрат

Подзадача 5 (10 баллов): \(S\) и \(T\) — треугольники

Подзадача 6 (16 баллов): \(S\) — строго выпуклый многоугольник, а \(T\) — удобный прямоугольник

Подзадача 7 (11 баллов): \(T\) — удобный прямоугольник

Подзадача 8 (19 баллов): нет дополнительных ограничений

Сегодня Денис проводит в ЛКШ клуб анонимных геометров. Он заготовил для клуба \(n\) выпуклых многоугольников, пронумерованных от \(1\) до \(n\). Он планирует предложить участникам клуба посчитать суммы Минковского этих многоугольников. А именно, он планирует дать \(q\) заданий, в \(i\)-м из них нужно посчитать сумму Минковского многоугольников с номерами от \(l_i\) до \(r_i\) включительно.

Суммой Минковского двух множеств \(A\) и \(B\) называется множество \(C = \{a + b : a \in A, b \in B\}\). Можно доказать, что если \(A\) и \(B\) являются выпуклыми многоугольниками, то \(C\) тоже будет выпуклым многоугольником.

Сумма двух выпуклых многоугольников

Чтобы посчитать сумму Минковского \(p\) многоугольников (\(p > 2\)), нужно посчитать сумму Минковского первых \(p - 1\) многоугольников, а потом сумму Минковского результата и \(p\)-го многоугольника.

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

Вам задан набор из n векторов на плоскости. Для каждого вектора разрешается домножить любые его координаты на -1. Таким образом, каждый вектор v_i = (x_i, y_i) можно преобразовать в один из следующих четырех векторов:

• v_i¹ = (x_i, y_i),
• v_i² = ( - x_i, y_i),
• v_i³ = (x_i,  - y_i),
• v_i⁴ = ( - x_i,  - y_i).

Вам нужно найти два вектора из набора и определить, какие из их координат следует умножить на -1 таким образом, чтобы модуль суммы полученных векторов был минимально возможным. Более формально, требуется выбрать два вектора v_i, v_j (1 ≤ i, j ≤ n, i ≠ j) и два числа k₁, k₂ (1 ≤ k₁, k₂ ≤ 4), так чтобы значение выражения |v_i^k₁ + v_j^k₂| было минимально.

Bob Bubblestrong just got a new job as security guard. Bob is now responsible for safety of a collection of warehouses, each containing the most valuable Bubble Cup assets - the high-quality bubbles. His task is to detect thieves inside the warehouses and call the police.

Looking from the sky, each warehouse has a shape of a convex polygon. Walls of no two warehouses intersect, and of course, none of the warehouses is built inside of another warehouse.

Little did the Bubble Cup bosses know how lazy Bob is and that he enjoys watching soap operas (he heard they are full of bubbles) from the coziness of his office. Instead of going from one warehouse to another to check if warehouses are secured, the plan Bob has is to monitor all the warehouses from the comfort of his office using the special X-ray goggles. The goggles have an infinite range, so a thief in any of the warehouses could easily be spotted.

However, the goggles promptly broke and the X-rays are now strong only enough to let Bob see through a single wall. Now, Bob would really appreciate if you could help him find out what is the total area inside of the warehouses monitored by the broken goggles, so that he could know how much area of the warehouses he needs to monitor in person.

Это упрощённая версия задачи. В этой версии \(n \le 2000\).

В трёхмерном пространстве заданы \(n\) различных точек, пронумерованных от \(1\) до \(n\). \(i\)-я точка имеет координаты \((x_i, y_i, z_i)\). Число точек \(n\) — чётное.

Вы хотели бы удалить все \(n\) точек, используя последовательность из \(\frac{n}{2}\) щелчков. За один щелчок вы можете удалить любые две ещё не удалённые точки \(a\) и \(b\), которые образуют идеально сбалансированную пару. Пара точек \(a\) и \(b\) идеально сбалансирована, если никакая другая точка \(c\) (которая ещё не удалена) не лежит в пределах минимального ограничивающего точки \(a\) и \(b\) прямоугольного параллелепипеда с рёбрами, параллельными осям координат.

Формально, точка \(c\) лежит внутри ограничивающего параллелепипеда точек \(a\) и \(b\) тогда и только тогда, когда \(\min(x_a, x_b) \le x_c \le \max(x_a, x_b)\), \(\min(y_a, y_b) \le y_c \le \max(y_a, y_b)\) и \(\min(z_a, z_b) \le z_c \le \max(z_a, z_b)\). Обратите внимание, что параллелепипед может быть вырожденным.

Найдите способ удалить все точки за \(\frac{n}{2}\) щелчков.

Это — интерактивная задача.

У Кханя есть \(n\) точек в декартовой системе координат, которые обозначаются как \(a_1, a_2, \ldots, a_n\). Все координаты точек — целые числа от \(-10^9\) до \(10^9\) включительно. Нет трех коллинеарных точек. Он говорит, что эти точки являются вершинами выпуклого многоугольника; другими словами, существует перестановка \(p_1, p_2, \ldots, p_n\) целых чисел от \(1\) до \(n\), такая, что многоугольник \(a_{p_1} a_{p_2} \ldots a_{p_n}\) является выпуклым и вершины перечислены против часовой стрелки.

Кхань дает вам число \(n\), но не координаты своих точек. Ваша задача — угадать вышеуказанную перестановку, задав несколько запросов. В каждом запросе вы даете Кханю \(4\) целых чисел \(t\), \(i\), \(j\), \(k\); где либо \(t = 1\), либо \(t = 2\); и \(i\), \(j\), \(k\) — это три различных индекса от \(1\) до \(n\) включительно. В ответ Хан говорит вам:

• Если \(t = 1\), то площадь треугольника \(a_ia_ja_k\) умноженную на \(2\).
• Если \(t = 2\), то знак векторного произведения двух векторов \(\overrightarrow{a_ia_j}\) и \(\overrightarrow{a_ia_k}\).

Напомним, что векторное произведение вектора \(\overrightarrow{a} = (x_a, y_a)\) и вектора \(\overrightarrow{b} = (x_b, y_b)\) — это целое число \(x_a \cdot y_b - x_b \cdot y_a\). Знак числа равен \(1\), если оно положительное, и \(-1\) иначе. Можно показать, что векторное произведение в запросах никогда не будет \(0\).

Вы можете задать не более \(3 \cdot n\) запросов.

Обратите внимание, что Кхань фиксирует координаты своих точек и не меняет их, отвечая на ваши запросы. Вам не нужно угадывать координаты. В вашей перестановке \(a_{p_1}a_{p_2}\ldots a_{p_n}\), \(p_1\) должен быть равен \(1\) и все индексы вершин должны быть перечисленны против часовой стрелки.

Сначала считайте целое число \(n\) (\(3 \leq n \leq 1\,000\)) — количество вершин.

Чтобы задать запрос, выведите \(4\) целых числа \(t\), \(i\), \(j\), \(k\) (\(1 \leq t \leq 2\), \(1 \leq i, j, k \leq n\)) на отдельной строке. \(i\), \(j\) и \(k\) должны быть различны.

После этого считайте ответ на запрос. Можно показать, что ответ на любой запрос всегда целое число.

Когда вы найдете перестановку, выведите \(0\). Затем выведите \(n\) целых чисел \(p_1, p_2, \ldots, p_n\) на той же строке.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Формат взломов

Для взломов используйте следующий формат:

Первая строка должна содержать целое число \(n\) (\(3 \leq n \leq 1\,000\)) — количество вершин.

\(i\)-я из следующих \(n\) строк должна содержать два целых числа \(x_i\) и \(y_i\) (\(-10^9 \le x_i, y_i \le 10^9\)) — координаты точки \(a_i\).

Вам дано множество из \(n\ge 2\) попарно различных точек с целыми координатами. Вы должны разделить эти точки на 2 непустые группы \(A\) и \(B\), чтобы следующее условие выполнялось:

Для любых двух точек \(P\) и \(Q\), напишите Евклидово расстояние между ними на доске: если они принадлежат одной и той же группе — желтым цветом, а если различным группам — синим цветом. Тогда ни одное желтое число не должно равняться ни одному синему числу.

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

Сейчас у Ани День рождения. Она позвала много гостей и приготовила для них один большой (почти бесконечный) праздничный торт, украшенный n кружочками банана разных размеров. Через 7 минут у Маши тоже будет День рождения, а пока Аня старше, она решила немного покомандовать. Она велела Маше разрезать торт k прямолинейными разрезами на несколько частей (разрезы могут пересекаться). В результате кружочки банана разделятся на кусочки.

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

С новым телом наш идол Арома Белая (или лучше было сказать Каори Минамийа?) начинает восстанавливать своё потерянное прошлое через OS-пространство.

Это пространство можно представить как 2D плоскость, с бесконечным количеством устройств с данными, пронумерованных с \(0\). Координаты устройств можно описать следующим образом:

• Координаты \(0\)-го устройства равны \((x_0, y_0)\)
• Для \(i > 0\), координаты \(i\)-го устройства равны \((a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)\)

Изначально Арома расположена в точке \((x_s, y_s)\). Она может находиться в OS-пространстве не более \(t\) секунд, после этого ей придётся вернуться в реальный мир. Чтобы вернутся в реальный мир не требуется возвращаться в изначальную точку \((x_s, y_s)\).

Внутри OS-пространства Арома может делать следующие действия:

• Из точки \((x, y)\) Арома может перейти в одну из следующих точек \((x-1, y)\), \((x+1, y)\), \((x, y-1)\) или \((x, y+1)\). Это действие занимает \(1\) секунду.
• Если Арома стоит в точке с устройством, то она может его собрать. Можно считать, что это действие занимает \(0\) секунд. Разумеется, каждое устройство можно собрать не более одного раза.

Арома хочет собрать как можно больше данных перед тем как вернётся назад. Помогите ей определить максимальное количество устройств с данными, которые она сможет собрать за \(t\) секунд.

\(n\) цистерн с водой стоят в ряд, \(i\)-я из них содержит \(a_i\) литров воды. Цистерны пронумерованны от \(1\) до \(n\) слева направо.

Вы можете выполнить следующую операцию: выбрать некоторый подотрезок \([l, r]\) (\(1\le l \le r \le n\)), и перераспределить воду с цистерн \(l, l+1, \dots, r\) между ними равномерно. Другими словами, заменить каждое из \(a_l, a_{l+1}, \dots, a_r\) на \(\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}\). К примеру, если для обьемов \([1, 3, 6, 7]\) вы выберете \(l = 2, r = 3\), вы получите обьемы \([1, 4.5, 4.5, 7]\). Вы можете выполнять данную операцию любое количество раз.

Какую лексикографически минимальную последовательность обьемов воды вы можете получить?

Напомним:

Последовательность \(a\) лексикографически меньше последовательности \(b\) равной длины, если и только если выполняется следующее: в первой (слева) позиции, где \(a\) и \(b\) отличаются, в последовательности \(a\) стоит меньший элемент, чем в \(b\).

Маленький Петя очень любит рисовать. Он нарисовал N красных и M синих точек на плоскости, причем так что никакие 3 из них не лежат на 1 прямой. Теперь ему интересно, сколько есть различных треугольников с вершинами в красных точках, не содержащих в себе ни одной синей точки.

У Бесси действительно много друзей, потому что она — всеми любимая корова! Ее новый друг Кролик пытается допрыгать до Бесси, чтобы поиграть вместе!

Точнее, он хочет попасть из \((0,0)\) в \((x,0)\), сделав несколько прыжков. Он готов прыгнуть из одной точки в другую на плоскости только если евклидово расстояние между этими точками равно одному из \(n\) его любимых чисел: \(a_1, a_2, \ldots, a_n\). За какое минимальное количество прыжков Кролик сможет добраться из \((0,0)\) в \((x,0)\)? Кролик может приземляться, в том числе, и в точки с нецелочисленными координатами. Можно доказать, что Кролик всегда может достигнуть точки назначения.

Напомним, что евклидово расстояние между точками \((x_i, y_i)\) и \((x_j, y_j)\) равно \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\).

Например, если любимые числа Кролика — это \(1\) и \(3\), то он может добраться из \((0,0)\) в \((4,0)\) за два прыжка (как показано ниже). Заметим, что существуют и другие способы добраться до \((4,0)\) за \(2\) прыжка (например, \((0,0)\) \(\rightarrow\) \((2,-\sqrt{5})\) \(\rightarrow\) \((4,0)\)).

Изображение соответствует первому набору входных данных из примера. Длина обоих прыжков равна \(3\), одному из любимых чисел Кролика.

Таким образом, перед каждым прыжком Кролик выбирает одно из чисел \(a_i\) и прыгает из текущей точки на расстояние ровно \(a_i\) в произвольном направлении. Одно и то же число он может выбирать любое количество раз.

Назовем граф с \(n\) вершинами, каждой из которых соответствует своя точка \(A_i = (x_i, y_i)\) с целыми координатами, планарным деревом, если:

• Все точки \(A_1, A_2, \ldots, A_n\) различны и никакие три точки не лежат на одной прямой.
• Граф является деревом, то есть в графе ровно \(n-1\) ребро и существует путь между любой парой вершин.
• Для всех пар ребер \((s_1, f_1)\) и \((s_2, f_2)\), таких что \(s_1 \neq s_2, s_1 \neq f_2,\) \(f_1 \neq s_2\) и \(f_1 \neq f_2\), отрезки \(A_{s_1} A_{f_1}\) и \(A_{s_2} A_{f_2}\) не пересекаются.

Представим планарное дерево на \(n\) вершинах. Рассмотрим выпуклую оболочку множества точек \(A_1, A_2, \ldots, A_n\). Давайте назовем это дерево паутиной если для всех \(1 \leq i \leq n\) следующие условия верны:

• Все листья (вершины со степенью \(\leq 1\)) лежат на выпуклой оболочке.
• Все вершины на выпуклой оболочке являются листьями.

Пример паутины:

Точки \(A_3, A_6, A_7, A_4\) лежат на выпуклой оболочке и вершины \(3, 6, 7, 4\) это все листья этого дерева.

Обратитесь к примечанию для большего количества примеров.

Давайте назовем подмножество \(S \subset \{1, 2, \ldots, n\}\) вершин поддеревом, если для всех пар вершин из \(S\) существует путь между ними, содержащий только вершины из множества \(S\). Обратите внимание, что любое поддерево планарного дерева также будет являться планарным деревом.

Вам дано планарное дерево, состоящее из \(n\) вершин. Назовем разбиение множества вершин \(\{1, 2, \ldots, n\}\) на непустые подмножества \(A_1, A_2, \ldots, A_k\) (то есть \(A_i \cap A_j = \emptyset\) для всех \(1 \leq i < j \leq k\) и \(A_1 \cup A_2 \cup \ldots \cup A_k = \{1, 2, \ldots, n\}\)) хорошим, если для всех \(1 \leq i \leq k\), множество \(A_i\) является поддеревом и паутиной. Два разбиения различны, если существует некоторое множество, лежащее в одном разбиении, но не лежащее в другом.

Найдите количество хороших разбиений. Поскольку это число может быть очень большим, найдите его по модулю \(998\,244\,353\).

Маленький Петя очень любит прямоугольники, а особенно квадраты. Недавно мама подарила ему 8 попарно не совпадающих точек на плоскости. Он решил разбить их на два множества по 4 точки так, чтобы точки из первого множества лежали в вершинах некоего квадрата, а из второго — в вершинах прямоугольника. Каждая из заданных 8 точек должна принадлежать ровно одному множеству. Допускается, чтобы прямоугольник из второго множества также был квадратом. Если разбиений несколько, Петю удовлетворит любое. Помогите ему найти одно такое разбиение. Обратите внимание, что и прямоугольник, и квадрат из разбиения должны иметь ненулевую площадь. Стороны фигур не обязательно должны быть параллельны осям координат.

Условие этой задачи почти полностью совпадает с условием задачи C1. Единственное отличие в следующем: в задаче C1 \(n\) всегда четно, а в задаче C2 \(n\) всегда нечетно.

Вам задан правильный многоугольник из \(2 \cdot n\) вершин (то есть он выпуклый и имеет равные стороны и углы) и все его стороны имеют длину \(1\). Назовем этот многоугольник \(2n\)-угольником.

Ваша задача — найти квадрат минимального размера, такой что в него можно вписать \(2n\)-угольник. \(2n\)-угольник можно вписать в квадрат, если \(2n\)-угольник можно разместить таким образом, что каждая точка, лежащая внутри или на границе \(2n\)-угольника также будет лежать внутри или на границе квадрата.

Вы можете вращать \(2n\)-угольник и/или квадрат.

Задан простой взвешенный связный неориентированный граф, состоящий из \(n\) вершин и \(m\) ребер.

Путем длины \(k\) в графе назовем последовательность из \(k+1\) вершины \(v_1, v_2, \dots, v_{k+1}\) такую, что для каждого \(i\) \((1 \le i \le k)\) ребро \((v_i, v_{i+1})\) присутствует в графе. У пути из вершины \(v\) вершина \(v_1=v\). Обратите внимание, что вершины и ребра могут входить в путь по несколько раз.

Вес пути — это сумма весов ребер в нем.

Для каждого \(i\) от \(1\) до \(q\) рассмотрим путь из вершины \(1\) длины \(i\) максимального веса. Чему равна сумма весов этих \(q\) путей?

Ответ может быть довольно большим, поэтому выведите его по модулю \(10^9+7\).

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

Ли считает правильный (выпуклый) \(n\)-угольник красивым тогда и только тогда, когда он может повернуть многоугольник таким образом, чтобы хотя бы одна из его сторон стала параллельна оси \(OX\) и хотя бы одна из его сторон стала параллельна оси \(OY\) одновременно.

Напомним, что правильный \(n\)-угольник — это выпуклый многоугольник из \(n\) вершин такой, что все его стороны и углы равны.

Ли пришел в магазин: в магазине продаются \(t\) правильных многоугольников. Для каждого из них выведите YES, если многоугольник красивый, или NO в противном случае.

После того, как вы получили 13 вердиктов time-limit-exceeded по ужасной геометрической задаче, вы решили сделать расслабляющий перерыв и позаниматься оригами.

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

Если вы согнете лист бумаги вдоль вертикальной прямой \(x=f\), какой будет площать полученной фигуры? Когда вы сгибаете лист, часть бумаги слева от прямой симметрично отражается с правой стороны.

Ваша задача ответить на \(q\) независимых запросов для значений \(f_1,\ldots,f_q\).

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

На плоскости с декартовой системой координат даны \(n\) непересекающихся горизонтальных отрезков с концами в целых точках. Все отрезки находятся строго над осью \(OX\). Вы можете выбрать произвольный вектор с координатами (\(a\), \(b\)), где \(b < 0\) и координаты — вещественные числа, и спроектировать все отрезки на ось \(OX\) вдоль этого вектора. При этом полученные проекции должны не пересекаться, но, возможно, могут касаться.

Вам нужно найти минимально возможную разницу между координатой \(x\) правого конца самой правой проекции и координатой \(x\) левого конца самой левой проекции.

Вам задан массив \(a_1, a_2, \dots , a_n\), отсортированный в порядке неубывания (\(a_i \le a_{i + 1})\).

Найдите три индекса \(i\), \(j\), \(k\), таких что \(1 \le i < j < k \le n\) и невозможно создать невырожденный треугольник (треугольник с ненулевой площадью) со сторонами \(a_i\), \(a_j\) и \(a_k\) (например, возможно создать невырожденный треугольник со сторонами \(3\), \(4\) и \(5\), но невозможно со сторонами \(3\), \(4\) и \(7\)). Или определите, что не существует таких три индекса.

Геральд накрывает новогодний стол. Стол имеет форму круга радиуса R. Геральд пригласил много гостей и обеспокоен вопросом, поместятся ли на столе тарелки для всех них. Считайте, что все тарелки круглые и имеют одинаковые радиусы, равные r. Каждая тарелка должна целиком помещаться на столе и касаться края стола. Разумеется, тарелки не должны пересекаться, однако могут касаться. Помогите Геральду определить, поместятся ли на столе n тарелок для гостей.

У вас есть квадрат размера \(10^6 \times 10^6\) на координатной плоскости с вершинами в точках \((0, 0)\), \((0, 10^6)\), \((10^6, 0)\) и \((10^6, 10^6)\).

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

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

Вот уже прошла почти половина зимы, и Маша мечтает о лете. Санки и коньки ей уже надоели, сегодня всю ночь ей снились классики. Это очень популярная детская игра, в которой игровое поле — классики — выглядит так, как показано на рисунке (все клетки квадратные и нумеруются снизу вверх, клетки в одной строке нумеруются слева направо). Опишем классики цифрами, которые обозначают количество квадратов в строке, начиная с нижней: 1-1-2-1-2-1-2-(1-2)..., где далее повторяется период (1-2).

Система координат задана так, как показано на рисунке. Стороны всех квадратов равны между собой и имеют длину a.

Маша очень умная и сообразительная девочка, и ее волнуют совсем недетские вопросы: если она бросит камешек в точку с координатами (x, y), то попадет ли она в какой-либо квадрат? В случае положительного ответа также требуется определить номер этого квадрата.

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

Юре поставлена задача построить замкнутое ограждение в форме произвольного невырожденного простого четырехугольника. Ему для этого выдали три прямых участка забора с известными длинами \(a\), \(b\), \(c\). Теперь ему нужно понять, какой длины должен быть четвертый участок забора \(d\), чтобы успешно построить ограждение. Ограждение должно быть в форме четырехугольника, стороны которого равны \(a\), \(b\), \(c\), \(d\). Помогите Юре, найдите любую подходящую длину.

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

Заключенный хочет сбежать из тюрьмы. Тюрьма является внутренней частью выпуклого многоугольника с вершинами \(P_1, P_2, P_3, \ldots, P_{n+1}, P_{n+2}, P_{n+3}\). Известно, что \(P_1=(0,0)\), \(P_{n+1}=(0, h)\), \(P_{n+2}=(-10^{18}, h)\) и \(P_{n+3}=(-10^{18}, 0)\).

Стены тюрьмы \(P_{n+1}P_{n+2}\), \(P_{n+2}P_{n+3}\) и \(P_{n+3}P_1\) очень высокие, и заключенный не может на них взобраться. Следовательно, его единственный шанс  — это достичь точки на одной из стен \(P_1P_2, P_2P_3,\dots, P_{n}P_{n+1}\) и сбежать оттуда. По периметру тюрьмы находятся два охранника. Заключенный движется со скоростью \(1\), в то время как охранники движутся, всегда оставаясь на периметре тюрьмы, со скоростью \(v\).

Если заключенный достигает точки на периметре, где есть охранник, охранник убивает заключенного. Если заключенный достигает точки, на которую он может взобраться, и там нет охранника, то он сразу же убегает. Изначально заключенный находится в точке \((-10^{17}, h/2)\), а охранники  — в точке \(P_1\).

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

Замечания:

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

Вам даны целое число \(k\) и \(n\) попарно различных точек с целочисленными координатами на евклидовой плоскости, \(i\)-я точка имеет координаты \((x_i, y_i)\).

Рассмотрим список всех \(\frac{n(n - 1)}{2}\) пар точек \(((x_i, y_i), (x_j, y_j))\) (\(1 \le i < j \le n\)). Для каждой такой пары выпишем расстояние от прямой, проходящей через эти две точки, до начала координат \((0, 0)\).

Ваша задача — вычислить \(k\)-е наименьшее число среди всех этих расстояний.

Utkarsh снова заставили играть в игры Ashish. Игроки ходят по очереди, Ashish ходит первым.

Рассмотрим плоскость. На нем стоит фишка, исходно в точке \((0,0)\). За один ход игрок может увеличить либо \(x\) координату, либо \(y\) координату фишки ровно на \(k\). Делая эти операции, игрок должен убедиться, что фишка остается в пределах (Евклидового) расстояния \(d\) от \((0,0)\).

Иначе говоря, если после хода координаты фишки \((p,q)\), должно быть выполнено \(p^2 + q^2 \leq d^2\).

Игра кончается, когда текущий игрок не может сделать ход. Можно доказать, что игра закончится за конечное число ходов. Определите, кто выигрывает при правильной игре обоих игроков.

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

Вдоль реки, около которой Аргус пасет Ио, растет \(n\) деревьев. Будем считать, что река это ось \(OX\) прямоугольной системы координат, а \(n\) деревьев это точки с \(y\) координатами равными \(0\). Также, есть еще одно дерево, растущее в точке \((0, 1)\).

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

The hobbits Frodo and Sam are carrying the One Ring to Mordor. In order not to be spotted by orcs, they decided to go through the mountains.

The mountain relief can be represented as a polyline with \(n\) points \((x_i, y_i)\), numbered from \(1\) to \(n\) (\(x_i < x_{i + 1}\) for \(1 \le i \le n - 1\)). Hobbits start their journey at the point \((x_1, y_1)\) and should reach the point \((x_n, y_n)\) to complete their mission.

The problem is that there is a tower with the Eye of Sauron, which watches them. The tower is located at the point \((x_n, y_n)\) and has the height \(H\), so the Eye is located at the point \((x_n, y_n + H)\). In order to complete the mission successfully, the hobbits have to wear cloaks all the time when the Sauron Eye can see them, i. e. when there is a direct line from the Eye to the hobbits which is not intersected by the relief.

The hobbits are low, so their height can be considered negligibly small, but still positive, so when a direct line from the Sauron Eye to the hobbits only touches the relief, the Eye can see them.

The Sauron Eye can't see hobbits when they are in the left position, but can see them when they are in the right position.

The hobbits do not like to wear cloaks, so they wear them only when they can be spotted by the Eye. Your task is to calculate the total distance the hobbits have to walk while wearing cloaks.

Nezzar любит игру osu!.

osu! играется на карте, которая может быть представлена как массив различных точек на плоскости. Карта называется красивой, если для любых трех последовательных точек \(A,B,C\), записанных в порядке следования в массиве, угол между этими тремя точками с центром в \(B\) будет строго меньше, чем \(90\) градусов.

Точки \(A,B,C\) слева образуют угол меньший, чем \(90\) градусов, поэтому они могут быть тремя последовательными точками в красивой карте; точки \(A',B',C'\) справа образуют угол, больший либо равный \(90\) градусам, поэтому они не могут быть тремя последовательными точками в красивой карте.

Сейчас у Nezzar есть карта, состоящая из \(n\) различных точек \(A_1,A_2,\ldots,A_n\). Nezzar хочет переупорядочить эти \(n\) точек так, чтобы получившаяся карта стала красивой.

Более формально, вы должны найти перестановку \(p_1,p_2,\ldots,p_n\) целых чисел от \(1\) до \(n\) такую, что карта \(A_{p_1},A_{p_2},\ldots,A_{p_n}\) будет красивой. Если это невозможно, вы должны определить это.

«Добытчик алмазов» — игра, похожая на «Добытчик золота», но в этой игре \(n\) шахтеров, а не \(1\).

Шахта может быть представлена как плоскость. Будем рассматривать \(n\) шахтеров как \(n\) точек, расположенных на оси y. В шахте расположены \(n\) алмазов, будем рассматривать их как \(n\) точек на оси x. По каким-то причинам ни шахтеры, ни алмазы не могут быть расположены в начале координат (точке \((0, 0)\)).

Каждый шахтер должен добыть ровно один алмаз. У каждого шахтера есть крюк, с помощью которого он может достать алмаз. Если шахтер, находящийся в точке \((a,b)\) использует свой крюк для добычи алмаза, расположенного в точке \((c,d)\), он потратит \(\sqrt{(a-c)^2+(b-d)^2}\) (расстояние между точками) единиц энергии. Шахтеры не могут перемещаться и помогать друг другу.

Цель игры — распределить алмазы по шахтерам так, чтобы минимизировать сумму затраченной энергии. Сможете ли вы найти этот возможный минимум?

В связи со специфическим инцидентом на баскетбольной тренировке, Akari придумал следующую задачу со спортивного программирования!

Вам даны \(n\) точек на плоскости, никакие три из которых не лежат на одной прямой. Изначально точка \(i\) имеет метку \(a_i\), причем метки \(a_1, a_2, \dots, a_n\) образуют перестановку чисел \(1, 2, \dots, n\).

Вы можете менять эти метки с помощью следующей операции:

1. Выберите два разных целых числа \(i\) и \(j\) между \(1\) и \(n\).
2. Поменяйте местами метки точек \(i\) и \(j\).
3. Нарисуйте отрезок между точками \(i\) и \(j\).

Последовательность операций корректна, если после применения всех операций в последовательности точка \(k\) имеет метку \(k\) для всех \(k\) от \(1\) до \(n\) включительно, и нарисованные отрезки не пересекаются внутри друг друга. Формально, если два отрезка пересекаются, то они должны сделать это в общей конечной точке обоих отрезков.

В частности, все нарисованные отрезки должны быть попарно различными.

Найдите любую корректную последовательность операций или определите, что ее нет.

После того, как Уово услышал историю доктора Чжан, он решил спланировать свой собственный полет вокруг света.

Он уже выбрал \(n\) контрольных точек на карте мира. Из-за формы рельефа и облаков, он не может лететь слишком высоко или слишком низко. Формально, пусть \(b_i\) будет высота самолета Уово на контрольной точке \(i\). Для всех целых \(i\) между \(1\) и \(n\) должно выполняться \(x_i^-\le b_i\le x_i^+\), где \(x_i^-\) и \(x_i^+\) — данные вам целые числа.

Угол полета самолета Уово тоже ограничен. Например, он не может лететь вертикально вверх под \(90\) градусов. Формально, \(y_i^-\le b_i-b_{i-1}\le y_i^+\) должно выполняться для всех целых \(i\) между \(2\) и \(n\), где \(y_i^-\) и \(y_i^+\) — данные вам целые числа.

Последнее ограничение связано со скоростью изменения угла. Самолет должен делать это плавно из соображений безопасности. Формально, \(z_i^- \le (b_i - b_{i-1}) - (b_{i-1} - b_{i-2}) \le z_i^+\) должно выполняться для всех целых \(i\) между \(3\) и \(n\), где \(z_i^-\) и \(z_i^+\) — данные вам целые числа.

Принимая во внимание все эти ограничения, Уово обнаружил, что выбрать высоты для контрольных точек слишком сложно. Помогите Уово определить, существует ли последовательность вещественных чисел \(b_1, \ldots, b_n\), удовлетворяющая всем ограничениям выше.

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

Участок Анни можно представить в виде бесконечной плоскости. Анни должна посадить \(n\) кустов картошки, \(i\)-й куст должен быть посажен в точке \((x_i,y_i)\). Анни начнет в точке \((0, 0)\), и за один шаг будет перемещаться на одну единицу длины вправо или вверх (т. е. увеличивать свою координату \(x\) или \(y\) на \(1\)). Из любой точки \((X,Y)\) в процессе движения она может посадить любое количество кустов в любых точках плоскости, используя свою картофельную пушку. Для посадки одного куста в точку \((x,y)\) требуется \(\max(|X-x|,|Y-y|)\) единиц энергии. Найдите минимальное количество энергии, необходимое для посадки всех кустов картошки.

Обратите внимание, что Анни может посадить любое количество кустов из любой точки.

В некоторой олимпиаде участвует \(n\) человек, причем они начинают олимпиаду с интервалом в \(x\) минут. Таким образом первый участник начнёт тур в момент времени \(0\), второй участник начнёт тур в момент времени \(x\), третий — в момент времени \(2 \cdot x\) и так далее.

Длительность тура для каждого участника составляет ровно \(t\) минут, то есть первый участник закончит в момент времени \(t\), второй — в момент времени \(t + x\), и так далее. Когда участник заканчивает писать тур, величина его недовольства равна числу других участников, которые в текущий момент времени еще пишут или только начинают писать тур, но еще не закончили его.

Определите, чему равно суммарное недовольство всех участников олимпиады.

Это простая версия задачи. Единственное отличие от сложной версии заключается в том, что в данной версии все координаты — четные числа.

Даны \(n\) столбов, расположенных в различных точках на плоскости. Гарантируется, что никакие три столба не лежат на одной прямой.

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

Грегор — член общества иллюминатов и хочет построить треугольный загон, соединив \(3\) различных существующих столба забором. Корова, находящаяся строго внутри загона, считается огражденной. Если ограждено нечётное число коров, и при этом площадь загона равна целому числу, то загон считается интересным.

Найдите количество интересных загонов.

Предположим, есть две точки \(p = (x_p, y_p)\) и \(q = (x_q, y_q)\). Тогда обозначим манхэттенское расстояние между ними как \(d(p, q) = |x_p - x_q| + |y_p - y_q|\).

Назовем три точки \(p\), \(q\), \(r\) как плохую тройку, если \(d(p, r) = d(p, q) + d(q, r)\).

Назовем массив \(b_1, b_2, \dots, b_m\) хорошим, если нельзя выбрать три различных индекса \(i\), \(j\) и \(k\) так, что точки \((b_i, i)\), \((b_j, j)\) и \((b_k, k)\) — плохая тройка.

Вам задан массив \(a_1, a_2, \dots, a_n\). Посчитайте количество хороших подмассивов \(a\). Подмассив массива \(a\) — это массив \(a_l, a_{l + 1}, \dots, a_r\) для некоторых \(1 \le l \le r \le n\).