Подскажите, правильно ли мыслю? Даны N точек на плоскости, координаты

которых положительные. Нужно уметь определять, можно ли покрыть все заданные точки плоскости тремя прямыми, каждая из которых параллельна одной из осей Х или У? Да, и каждая прямая должна проходить через, как минимум, две точки.
Моя идея состоит в том, чтобы сначала разбить точки на группы из как минимум двух точек с одинаковой координатой по х. Если таких групп три, то выигрыш. Иначе сделать аналогичное по другой координате. Если все ещё не выигрыш, то нужно найти точку, которая лежит в двух группах (совпадение по х, совпадение по у), удалить все точки этих групп. Если оставшиеся точки можно распределить в группу по совпавшим х или по у, то это победа, иначе нельзя

А на тесте: 0 0 0 2 1 1 3 1 2 3 4 3 работает?

Так это ж vertex cover?

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

Непонятно, не вижу граф.

Вершины -- координаты по Х и Y, ребра между X и Y если есть точка (X,Y)

Можно решить за O(n log n) следующим образом. Для начала, как Вы и сказали, проверим, можно ли просто провести 3 прямые одного типа. Если не получилось, то понятно, что у нас всегда будет одна прямая одного типа и две другого. Научимся решать задачу для случаев, когда проводим одну вертикальную прямую (для горизонтальных аналогично). Для этого пройдёмся по всем уникальным значениям x, поддерживая также мапу вида {y-координата: кол-во точек с такой y-координатой}. Для каждой из перебираемых линий сначала удалим все точки с такой x-координатой из мапы, отдельно поддерживая количество y-координат с ненулевым кол-вом точек на ней. После за O(1) проверим, можно ли провести две горизонтальные прямые или нет, ну и вернём удалённые точки в мапу. Поскольку каждая точка будет удалена ровно 1 раз, получим O(n log n) (там ещё возможно нужно будет где-то сортировку делать, так что лог не только от мапы). Аналогично сделаем для случая одной горизонтальной прямой.

То есть нужно в случае одной вертикальной прямой, нужно из мапы удалить все Х, шагая по уникальным Х, такие что они гарантированно не могут попасть на горизонтальную прямую, то есть те, с которыми по У никакая точка не совпадает?

Частотный анализ?

Можно для экономии памяти сделать 2 прохода на одной мапе

Вот же биекция