Сканирующая прямая

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

Точка \(x\) принадлежит отрезку \([l, r]\), если \(l \le x \le r\) (концы включены).

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — минимальное количество точек.

Примечание

В первом примере четыре отрезка: \([1, 6]\), \([2, 8]\), \([7, 12]\), \([10, 16]\). Точки \(x = 6\) и \(x = 10\) вместе попадают в каждый из отрезков: \(6\) — в первые два, \(10\) — в последние два. Меньше двух точек не хватит — отрезки \([1, 6]\) и \([10, 16]\) не пересекаются, одной общей точки у них нет.

Во втором примере все три отрезка содержат точку \(x = 5\), так что одной точки достаточно.

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

Найдите сумму длин пересечений по всем парам.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — сумма длин пересечений по всем неупорядоченным парам отрезков. Ответ может не помещаться в 32-битный тип.

Примечание

В первом примере три отрезка: \([0, 10]\), \([2, 6]\), \([8, 15]\).

• Пересечение первого и второго — \([2, 6]\) длины \(4\).
• Пересечение первого и третьего — \([8, 10]\) длины \(2\).
• Пересечение второго и третьего пусто.

Сумма: \(4 + 2 + 0 = 6\).

Во втором примере четыре одинаковых отрезка длины \(10\). Каждая из \(\binom{4}{2} = 6\) пар даёт пересечение длины \(10\), итого \(60\).

На числовой прямой даны \(n\) отрезков. Назовём глубиной отрезка \(i\) количество отрезков \(j\) (включая сам отрезок \(i\)), которые целиком его содержат: \(l_j \le l_i\) и \(r_i \le r_j\).

Найдите максимальную глубину среди всех данных отрезков.

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

В первой строке — целое число \(n\) (\(1 \le n \le 5000\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — максимальная глубина.

Примечание

В первом примере отрезок \([3, 4]\) содержится в \([2, 5]\), который, в свою очередь, содержится в \([1, 10]\). Глубина \([3, 4]\) равна \(3\): его содержат он сам, \([2, 5]\) и \([1, 10]\). Это максимум.

Во втором примере все три отрезка совпадают, и каждый «содержится» в каждом — глубина равна \(3\).

На числовой прямой даны \(n\) отрезков. Требуется разбить их на минимальное число групп так, чтобы внутри каждой группы любые два отрезка не пересекались. При этом стыковка концом-к-началу пересечением не считается: отрезки \([a, b]\) и \([b, c]\) могут попасть в одну группу.

Найдите минимальное возможное число групп.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(0 \le l_i < r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — минимум групп.

Примечание

В первом примере отрезки \([0, 30]\), \([5, 10]\), \([15, 20]\), \([25, 35]\). В одну группу можно положить \([5, 10]\), \([15, 20]\) и \([25, 35]\) — они попарно не пересекаются. Отрезок \([0, 30]\) пересекается с каждым из них и требует отдельной группы. Итого: \(2\).

Во втором примере отрезки \([10, 20]\) и \([20, 30]\) стыкуются по точке \(20\), и по условию это не считается пересечением. Поэтому одной группы достаточно.

На числовой прямой задан целевой отрезок \([L, R]\) и \(n\) отрезков-«покрывал». Определите, покрывают ли эти \(n\) отрезков целевой отрезок целиком — то есть каждая точка из \([L, R]\) принадлежит хотя бы одному из них.

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

В первой строке — два целых числа \(L\) и \(R\) (\(-10^9 \le L \le R \le 10^9\)) — концы целевого отрезка.

Во второй строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка-покрывала.

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

Выведите YES, если каждая точка целевого отрезка \([L, R]\) покрыта хотя бы одним из данных отрезков, и NO иначе.

Примечание

В первом примере отрезки \([0, 4]\), \([3, 7]\), \([6, 10]\) вместе покрывают всю цель \([0, 10]\) без пропусков.

Во втором примере между точками \(4\) и \(6\) есть пропуск (точка \(5\) не покрыта ни одним отрезком), поэтому ответ NO.

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

Найдите суммарную длину закрашенной части прямой.

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

В первой строке — целое число \(n\) (\(1 \le n \le 10^5\)).

В каждой из следующих \(n\) строк — два целых числа \(l_i\) и \(r_i\) (\(-10^9 \le l_i \le r_i \le 10^9\)) — концы очередного отрезка.

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

Одно целое число — длина объединения всех данных отрезков.

Примечание

В первом примере отрезки \([1, 5]\) и \([3, 7]\) сливаются в один отрезок \([1, 7]\) длины \(6\). Отдельный отрезок \([10, 12]\) добавляет ещё \(2\). Итого: \(8\).

Во втором примере четыре отрезка стыкуются концом-к-началу и образуют один сплошной отрезок \([0, 4]\) длины \(4\).

Ночью на сибирской трассе одновременно сошло \(n\) снежных заносов. Каждый занос перекрывает участок дороги между километровыми отметками \(a_i\) и \(b_i\) включительно. Сообщения о заносах поступали диспетчеру по рации в произвольном порядке, поэтому \(a_i\) может оказаться как меньше, так и больше \(b_i\): занос покрывает все километровые отметки от \(\min(a_i, b_i)\) до \(\max(a_i, b_i)\) включительно.

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

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

В первой строке записаны два целых числа \(n\) и \(m\) (\(1 \le n, m \le 50\,000\)) — количество заносов и количество запросов.

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

В последней строке через пробел записаны \(m\) целых чисел \(p_1, p_2, \ldots, p_m\) (\(-10^9 \le p_j \le 10^9\)) — километровые отметки, о которых спрашивают водители.

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

Выведите \(m\) целых чисел через пробел: для каждой отметки \(p_j\) — количество заносов, перекрывающих этот километр.

Примечание

Точка считается принадлежащей участку с концами \(a\) и \(b\), если выполняется неравенство \(\min(a, b) \le p \le \max(a, b)\). Совпадение с границей засчитывается.

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

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

Входные данные
Первая строка содержит одно целое число n (0 ≤ n≤ 100 000) – количество черных узлов в начале. Каждая из следующих n строк содержит два целых числа – координаты очередного черного узла, по модулю не превосходящие 10⁹.

Выходные данные
Выведите число черных вершин после окончания всех перекрасок. Если процедура никогда не закончится, то выведите –1.

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

Входные данные
Сначала вводятся числа N - количество вершин N-угольника (3 <= N <= 1000) и M - количество диагоналей, проведенных Васей. Далее на вход программы поступают M пар чисел, задающих диагонали (каждая диагональ задается парой номеров вершин, которые она соединяет). Гарантируется, что каждая пара чисел задает диагональ (то есть две вершины различны и не являются соседними), а также что никакие две пары не задают одну и ту же диагональ. Никакие две диагонали не пересекаются внутри N-угольника. Вершины N-угольника нумеруются числами от 1 до N.

Выходные данные
Если Васино утверждение верно, то программа должна выводить единственное число 0. В противном случае необходимо вывести сначала число K - количество вершин в какой-нибудь не треугольной части. Далее должно быть выведено K чисел - номера вершин исходного N-угольника, которые являются вершинами этой K-угольной части в порядке обхода этой части.

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

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

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

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

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

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

• Отрезок: <<segment \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) и \((x_2, y_2)\) — концы отрезка, отрезок считается направленным от \((x_1, y_1)\) к \((x_2, y_2)\).

• Луч, направленный от начала: <<outray \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) — начало луча, а \((x_2, y_2)\) — произвольная точка на луче, отличная от начала.

• Луч, направленный к началу: <<inray \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_2, y_2)\) — начало луча, а \((x_1, y_1)\) — произвольная точка на луче, отличная от начала.

• Прямая: <<line \(x_1\) \(y_1\) \(x_2\) \(y_2\)>>, где \((x_1, y_1)\) и \((x_2, y_2)\) — две точки на прямой, причем при движении вдоль прямой в ее направлении точка \((x_1, y_1)\) следует ранее точки \((x_2, y_2)\).

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

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


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

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).

Главный Судья гонок хочет определить порядок, в котором должны стартовать скутеры, чтобы аварии не произошло. Например, в ситуации, приведенной на рисунке, сначала должен стартовать скутер номер 2 (если попытается стартовать скутер номер 1 или 3, то он столкнется со скутером номер 2). После этого скутеры 1 и 3 могут стартовать в любом порядке (они друг другу не мешают).

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

Входные данные
В первой строке вводится натуральное число N( 1 ≤ N ≤ 30 000).

В каждой из следующих N строк содержится по 6 чисел: x₁, y₁, x₂, y₂, x₃, y₃ – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 10⁶. В начальный момент скутеры не задевают друг друга.

Выходные данные
Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.

Примечание
Первый тест соответствует приведенному рисунку. Ответ 2 3 1 в этом тесте также является правильным
 

На вокзале есть K тупиков, куда прибывают электрички. Этот вокзал является их конечной станцией, поэтому электрички, прибыв, некоторое время стоят на вокзале, а потом отправляются в новый рейс (в ту сторону, откуда прибыли).

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

Тупики пронумерованы числами от 1 до K. Когда электричка прибывает, ее ставят в свободный тупик с минимальным номером. При этом если электричка из какого-то тупика отправилась в момент времени X, то электричку, которая прибывает в момент времени X, в этот тупик ставить нельзя, а электричку, прибывающую в момент X+1 — можно.

Напишите программу, которая по данному расписанию для каждой электрички определит номер тупика, куда прибудет эта электричка.

Входные данные
Сначала вводятся число K — количество тупиков и число N — количество электропоездов (1≤K≤100000, 1≤N≤100000). Далее следуют N строк, в каждой из которых записано по 2 числа: время прибытия и время отправления электрички. Время задается натуральным числом, не превышающим 10⁹. Никакие две электрички не прибывают в одно и то же время, но при этом несколько электричек могут отправляться в одно и то же время. Также возможно, что какая-нибудь электричка (или даже несколько) отправляются в момент прибытия какой-нибудь другой электрички. Время отправления каждой электрички строго больше времени ее прибытия.

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

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

Фермер Джон продолжает бороться за здоровье своих коров.
Имеется N cows (1≤N≤1000) коров, некоторые из которых больны. Коровы выстроены в ряд (на числовой прямой), корова i стоит на позиции x_i. ФД знает что если другая корова находится в радиусе R от больной, то она тоже заболевает. А потом заболевают коровы, которые находятся в радиусе R от этой и т.д.

К несчастью, ФД не знает точное значение R. Однако он знает, какие из его коров больны. По этим данным определите минимальное количество изначально инфицированных болезнью коров.

Входные данные
Первая строка ввода содержит N. Каждая из последующих N строк описывает одну корову двумя числами x и s, где x - позиция коровы, а s равно 0 для здоровой коровы и 1 для больной. Как минимум 1 корова больна. И все коровы, которые могли стать больными от распространения болезни уже больны.
Выходные данные
Определите минимальное количество коров, которые изначально были больны, перед любым распространением болезни.

Примеры

№	Входные данные	Выходные данные
1	6 7 1 1 1 15 1 3 1 10 0 6 1	3