Бинарный поиск

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

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

Степень точки \(A\) относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке \(A\), имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки \(A\) до некоторой точки многоугольника: \(d_{min}\) и \(d_{max}\). Степенью точки относительно данного многоугольника назовем минимум величины \(d_{min}\times d_{max}\) по всем таким лучам.

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

Будем считать, что наблюдательный центр находится в точке \((0, 0)\). Входной файл содержит описание полигона.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин полигона (\(3 \le n \le 100\)). Следующие \(n\) содержат по два вещественных числа — координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают \(1000\) по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.

Формат выходных данных
Выведите одно число — степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на \(10^{-4}\).

На день рождения Пете подарили коробку кубиков. На каждом кубике написано некоторое целое число. Петя выложил все n своих кубиков в ряд, так что числа на кубиках оказались расположены в некотором порядке a[1], a[2],...,a[n]. Теперь он хочет раскрасить кубики в разные цвета таким образом, чтобы для каждого цвета последовательность чисел на кубиках этого цвета была строго возрастающей. То есть, если кубики с номерами i[1], i[2],..., i[k] покрашены в один цвет, то a[i[1]] < a[i[2]] < ... < a[i[k]]. Петя хочет использовать как можно меньше цветов. Помогите ему!

Первая строка входного файла содержит число n - количество кубиков у Пети (1 <= n <= 250000). Затем следует n чисел, разделенных пробелами и/или переводами строки - a[1], a[2], ..., a[n].

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

В одном королевстве есть \(n\) городов, расположенных вдоль длинной прямой дороги, \(i\)-й город расположен на расстоянии \(x_i\) километров от начала дороги (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

В ближайшее время король планирует провести реформу управления королевством и разделить его на \(k\) провинций. Каждый город должен войти ровно в одну провинцию.

В каждую провинцию войдет от \(a\) до \(b\) городов, причем эти города должны иметь следующие подряд номера. Таким образом, каждая провинция характеризуется числами \(i\) и \(l\), для которых \(1 \le i\), \(i + l - 1 \le n\), \(a \le l \le b\) и в провинцию входят города с номерами \(i, i + 1, \ldots, i + l - 1\).

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

Формат входных данных
Первая строка ввода содержит четыре целых числа: \(n\), \(k\), \(a\) и \(b\) (\(1 \le n \le 200\), \(1 \le k \le n\), \(1 \le a \le b \le n\), \(ak \le n \le bk\)). Вторая строка ввода содержит \(n\) целых чисел: \(x_1, x_2, \ldots, x_n\) (\(0 \le x_1 < x_2 < \ldots < x_n \le 10^9\)).

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

Примечание
В примере оптимально первые 4 города объединить в первую провинцию, а пятый и шестой — во вторую. Максимальное расстояние между двумя городами в одной провинции: \(13 - 6 = 7\).

Примеры

3 2
2 6
3 4 5

1
1

3 2
1 6
4 3 5

0

3 5
1 7
5 3 4

3 
2
3
1

Примеры