Недавно Петя занялся изучением древних цивилизаций. Он нашел в энциклопедии даты рождения и гибели \(N\) различных древних цивилизаций и теперь хочет узнать о влиянии культуры одних цивилизаций на культуру других.
Петя предположил, что между цивилизациями \(A\) и \(B\) происходил культурный обмен, если они сосуществовали в течение некоторого ненулевого промежутка времени. Например, если цивилизация A зародилась в 600 году до н.э. и существовала до 400 года до н.э., а цивилизация B зародилась в 450 году до н.э. и существовала до 300 года до н.э., то культура каждой из этих цивилизаций оказывала влияние на развитие другой цивилизации в течение 50 лет. В то же время, если цивилизация C зародилась в 400 году до н.э. и существовала до 50 года до н.э., то она не смогла осуществить культурного обмена с цивилизацией A, в то время как культурный обмен с цивилизацией B продолжался в течение 100 лет.
Теперь для выполнения своих исследований Петя хочет найти такую пару цивилизаций, культурный обмен между которыми имел место на протяжении наименьшего ненулевого промежутка времени. Помогите ему!
В первой строке вводится число \(N\) – количество цивилизаций, культура которых интересует Петю (1\( \le\)N\( \le\)100 000). Следующие N строк содержат описание цивилизаций – в каждой строке задаются два целых числа \(S_i\) и \(E_i\) – год зарождения и год гибели соответствующей цивилизации. Все числа не превосходят \(10^9\) по абсолютной величине, \(S_i\) < \(E_i\).
Выведите два числа – номера цивилизаций, периоды существования которых имеют наименьшее ненулевое пересечение. Если никакие две цивилизации не пересекаются во времени, выведите единственное число 0.
3 -600 -400 -450 -300 -400 -50
1 2
2 10 20 15 21
1 2
1 77777 77778
0
Множество на плоскости называется выпуклым, если вместе с любыми двумя точками оно содержит также и отрезок, соединяющий эти точки. Минимальное по включению выпуклое множество, содержащее заданное множество точек \(X\), называется выпуклой оболочкой множества \(X\).
В этой задаче вам требуется найти выпуклую оболочку множества точек, принадлежащих заданному набору углов.
Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.
На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.
В первой строке вводится число \(n\) - количество углов (1 <= \(n\) <= 1000). Каждая из следующих n строк содержит описание одного угла. Угол задается координатами трех точек: вершины и двух отличных от вершины точек - по одной на каждом из лучей. Все координаты целые и не превышают \(10^4\) по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.
Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходных данных не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все выводимые числа должны быть целыми и не превосходить \(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.
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 0 0 -1 0
2 0 0 1 0 0 1 0 0 -1 0 0 -1
0
Организаторы детского праздника планируют надуть для него \(M\) воздушных шариков. С этой целью они пригласили \(N\) добровольных помощников, \(i\)-й среди которых надувает шарик за \(T_i\) минут, однако каждый раз после надувания \(Z_i\) шариков устает и отдыхает \(Y_i\) минут. Теперь организаторы праздника хотят узнать, через какое время будут надуты все шарики при наиболее оптимальной работе помощников, и сколько шариков надует каждый из них. (Если помощник надул шарик, и должен отдохнуть, но больше шариков ему надувать не придется, то считается, что он закончил работу сразу после окончания надувания последнего шарика, а не после отдыха).
В первой строке входных данных задаются числа \(M\) и \(N\) (0 <= \(M\) <= 15000, 1 <= \(N\) <= 1000). Следующие \(N\) строк содержат по три целых числа - \(T_i\), \(Z_i\) и \(Y_i\) соответственно (1 <= \(T_i\), \(Y_i\) <= 100, 1 <= \(Z_i\) <= 1000).
Выведите в первой строке число \(T\) - время, за которое будут надуты все шарики. Во второй строке выведите \(N\) чисел - количество шариков, надутых каждым из приглашенных помощников. Разделяйте числа пробелами. Если распределений шариков несколько, выведите любое из них.
2 2 1 1 1 1 1 1
1 1 1
3 2 2 2 5 1 1 10
4 2 1
У Коли сегодня день рождения! По этому случаю он решил после олимпиады сходить с друзьями в парк аттракционов. И какая удача — можно купить групповой билет сразу на всех, всего за \(S\) рублей!
Конечно, скидываться придется всем поровну. То есть, если Коля позовет \(k\) своих друзей, то каждому придется заплатить \(S/(k + 1)\) рублей (да, сам Коля тоже должен внести свою долю). При этом \(S\) не обязательно должно делиться на \(k + 1\): главное — купить билет, а между собой друзья уж как-нибудь договорятся.
Всего у Коли \(n\) друзей, при этом \(i\)-й из них готов пойти с Колей в парк, если доля, которую ему придется заплатить не больше \(b_i\) (больше денег у него просто с собой нет) и не меньше \(a_i\) (иначе он решит, что Колин день рождения — это скучно, и пойдет играть в волейбол с Сережей).
Так что может так получиться, что всех позвать не удастся. Ну и ладно. Для каждого своего друга Коля знает число \(f_i\) — количество веселья, который тот произведет, если его позвать.
Помогите Коле выбрать подмножество друзей, которых Коля должен позвать с собой, чтобы максимизировать суммарное веселье.
В первой строке входного файлы содержится два целых числа: \(n\) и \(S\) (\(1 \le n \le 100\,000\), \(0 \le S \le 10^9\)) — количество друзей Коли и стоимость билета. В следующих \(n\) строках содержится по три целых числа: в \(i\)-й из этих строк находятся числа \(a_i\), \(b_i\) и \(f_i\) (\(0 \le a_i \le b_i \le S\), \(0 \le f_i \le 10^9\)). Они означают, что \(i\)-го друга можно позвать на вечеринку, если доля, которую ему придется заплатить, лежит между \(a_i\) и \(b_i\), и он произведет \(f_i\) веселья.
В первой строке выходного файла выведите два числа: \(k\) (количество приглашенных на вечеринку друзей) и \(F\) (максимальное суммарное веселье, которое можно получить). Во второй строке выведите \(k\) чисел — номера друзей, которых нужно пригласить.