С++ , Разделение королевства Разделение королевства
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более удобного составления карт в Флатландии была введена Декартова система координат. Известно, что i-й замок находится в точке с координатами (xi+0.5, yi+0.5), где xi, yi — целые числа. Местоположения всех замков попарно различны.

На старости лет король решил разделить на карте королевство между своими сыновьями прямыми, параллельными осям координат. Если прямая параллельна оси Ox, то у-координата всех точек на прямой должна быть целым числом, иначе x-координата у всех точек должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не должны превышать 2⋅109. При этом Его величество хочет, чтобы после разделения королевства любые два замка оказались в различных частях.

королю разделить королевство, используя не более чем n−1 прямую. У любой пары прямых должно быть не более одной общей точки.

Входные данные

В первой строке задано целое число n (1≤n≤100000) — количество замков в королевстве. В следующих n строках записаны по два числа xi и yi (−109≤xi≤109, −109≤yi≤109) — целые части координат замков.

Выходные данные

В первой строке выходного файла выведите количество используемых прямых. В следующих строчках выведите сами прямые, по одной в каждой строке. Если прямая параллельна оси Ox, то выведите символ "y", а затем через пробел y-координату всех точек на этой прямой, иначе выведите символ "x", а затем через пробел x-координату всех точек на этой прямой.

Примеры
Ввод
Вывод
4
0 2
0 3
1 2
1 3
2
y 3
x 1

👇

Открыть все ответы

Ответ:

Tigrmigr

09.05.2020

I. Последовательность действий

- Выделить массив от a[l] до a[r], где a - сортируемый массив, а l & r - крайний левый и крайний правый сортируемый елемент

- Провести сравнение елементов попарно двигаясь слева на право, если первый елемент больше второго - необходимо поменять их местами

- Откинуть крайнеправый елемент из сортируемого участка

- Провести сравнение елементов попарно двигаясь справа на лево, если первый елемент меньше второго - необходимо поменять их местами

- Откинуть крайне левый элемент из сортируемого участка

- Повторить с начала пока не останется сортируемых элементов

II. Оптимизация

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

III. Пример сортировки

Элементы что находятся в текущем под массиве - выделены [] скобками.

Элементы что сравниваются в текущей итерации выделены ()

[(33 55) 25 7 16 45 22 30 41 83 12 17 31 77] | 33 < 55 -> пропускаем

[33 (55 25) 7 16 45 22 30 41 83 12 17 31 77] | 55 > 25 -> меняем местами

...

7 12 16 [17 22 25 30 31 (33 41) 45] 55 77 83 | 33 < 41 -> пропускаем

7 12 16 [17 22 25 30 31 33 (41 45)] 55 77 83 | 41 < 45 -> пропускаем

Так как на протяжении всего прохода по под массиву не было перемещений -> сортировка завершена.

(Полное решение представлено в прикрепленной картинке)

Кол-во сравнений при оптимизации сортировки: 71

Если считать кол-во сравнений в сортировке без оптимизации (либо в самом неудачном раскладе сорируемого массива) то его можно будет посчитать так:

кол-во сравнений 2n - 3 - для прохода по подмостиву туда и обратно (n - кол-во элементов массива)

кол-во сравнений в сортировке - сумма сравнений для прохода по каждому из под массивов туда и обратно

кол-во под массивов в массиве будет равно n / 2

Соответственно имеем формулу $\sum_{i=n}^{i1}(2n-3)_{i};i=i-2$ , или же другими словами: сумма элементов (2i - 3) от i, где i = n, пока i > 1, когда i = i - 2.