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

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

Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того, чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы i-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере p_i условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.

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

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью a_i, а каждый эльф – темпераментом b_i. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо \( b_j \lt a_i \lt b_k \), либо \( b_k \lt a_i \lt b_j\).

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

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

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

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

Степень точки A относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке A, имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки A до некоторой точки многоугольника: d_min и d_max. Степенью точки относительно данного многоугольника назовем минимум величины d_min×d_max по всем таким лучам.

Военные не справляются с задачей вычисления степени наблюдательного центра относительно полигона и решили подключить к этой задаче вас. Помогите им!

В некотором царстве, в некотором государстве было \(N\) городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |\(x_1\) - \(x_2\)| + |\(y_1\) - \(y_2\)|.

Император решил построить \(N\)+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

Нелегкая задача выбрать место для столицы поручена Вам.

Администрация одного института решила построить в холле фонтан. По плану администрации, фонтан должен иметь форму круга с максимально возможным радиусом. Дизайнеру сообщили, что холл института имеет вид прямоугольника, размером \(X\)×\(Y\) метров. Однако когда дизайнер стал выбирать место для фонтана, он столкнулся с серьезной проблемой: в холле института обнаружилось \(N\) круглых колонн, снести которые не представляется возможным.

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