Задачка про надмножество

[Equinoxe]

Множество точек на плоскости называется хорошим, если для любых двух точек выполняется хотя бы одно из трех условий:
— эти две точки лежат на одной горизонтали;
— эти две точки лежат на одной вертикали;
— внутри или на границе прямоугольника с углами в этих двух точках есть другие точки множества, помимо этих двух. Здесь имеется в виду прямоугольник со сторонами, параллельными осям координат.

На плоскости задано множество из $n$ точек $(n \leq 10^4)$. Можно ли дополнить его до хорошего, содержащего при этом не более $2 \cdot 10^5$ точек?

Уточнение 1: разные точки имеют и должны иметь разные координаты
Уточнение 2: все точки имеют и должны иметь целые координаты


Такая вот сегодня задачка! Взята из только что окончившегося финала Яндекса

[Sirion]

Какая забавная очевидная задачка ^^

Везде далее будем опускать слово "целочисленный", но иметь в виду, что мы работаем только с целочисленными объектами.
Скажем, что две точки находятся в хороших отношениях, если для них выполняется одно из трёх условий (см. выше). Толщиной множества точек назовём мощность множества их ординат.

Проведём горизонтальную прямую через одну из точек так, чтобы толщина множеств точек над ней и под ней различалась не более чем на единицу (думаю, достаточно очевидно, что мы можем это сделать). Спроектируем на неё все точки нашего множества, в точках проекций поставим новые точки надмножества (их получится не более 10000). Теперь порадуемся следующим фактам:
1) Точки на прямой находятся в хороших отношениях со всеми остальными точками.
2) Точки "верхнего" множества находятся в хороших отношениях с точками "нижнего" множества.

Теперь повторим эту операцию отдельно с "верхним" и с "нижним" множествами. Количество точек надмножества увеличится ещё не более чем на 10000, далее повторим для получившихся четырёх множеств и т.д.

Суть такова, что на энном шаге толщина каждого из множеств разбиения не превышает $10000/2^n$. Таким образом, уже на тринадцатом шаге (мощность надмножества к этому моменту не превышает 140000) толщина этих множеств будет не больше единицы. Однако очевидно, что в множестве толщины единица все точки находятся в хороших отношениях. Отсюда нам счастье.

[Equinoxe]

Sirion, да, всё именно так :)
Самая хорошая (и хорошодоказуемая по индукции) оценка сверху пока что $2n \lceil \log_4 n \rceil $