Шестиугольный рисунок
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин (один из миньонов) увлекся рисованием на шестиугольных решетках. Шестиугольной решеткой называется решетка, разбивающая плоскость на равные правильные шестиугольники. Каждый шестиугольник однозначно соответствует паре целочисленных координат, где первая ось координат направлена строго вниз, а вторая — под углом $$$120^\circ$$$ к ней. Рисунок, изображающий решетку и систему координат, можно видеть ниже:

Разумеется, решетка продолжается бесконечно во все стороны, но для удобства изображена только ее часть. Внутри каждой ячейки написаны ее координаты. Для ячейки $$$(1, 2)$$$ стрелками показано, как найти ее координаты на осях координат.

Две ячейки называются соседними, если их границы имеют общую сторону. Например, ячейки $$$(1, 3)$$$ и $$$(2, 2)$$$ — соседние, а $$$(1, 3)$$$ и $$$(3, 2)$$$ — нет. Множество ячеек называется связным, если от любой ячейки множества до любой можно «добраться», двигаясь каждый раз в ячейку из множества, соседнюю с предыдущей, и двусвязным, если между любыми двумя ячейками множества существует хотя бы два непересекающихся по ячейкам пути.

Сегодня Стюарт и Боб закрасили некоторое (не обязательно связное) множество из $$$n$$$ ячеек этой решетки, и показали Кевину. Начинающий художник считает множество красивым, если в нем нет трех взаимно соседних ячеек (имеющих общую точку на границах). Будем называть три такие ячейки треугольным скоплением.

Теперь Кевину интересно, какие ячейки следует стереть с рисунка, чтобы в нем не осталось треугольных скоплений. Разумеется, некрасивым рисунком он хвастаться Грю не будет, но, чтобы не портить изначальную задумку Стюарта и Боба, ему хочется стереть как можно меньше закрашенных ими ячеек.

Помогите ему с этой задачей; от вас не требуется найти минимальное количество ячеек, которое надо удалить, однако чем меньше ячеек удаляется вашим решением, тем больше баллов оно наберет.

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

В первой строке ввода через пробел даны два целых числа $$$n$$$, $$$\mathtt{cost}$$$ и $$$\gamma$$$ — количество закрашенных ячеек на рисунке, который получил Кевин ($$$1 \le n \le 10^5$$$), а также стоимость данного теста и нижняя граница на допустимую точность (см. секцию «Система оценки»). Параметры $$$\mathtt{cost}$$$ и $$$\gamma$$$ служат для оценки вашего ответа чекером и не обязаны использоваться в вашем решении.

В следующих $$$n$$$ строках перечислены координаты ячеек, входящих в множество. В $$$i$$$-й строке через пробел даны два целых числа $$$x_i$$$ и $$$y_i$$$ — координаты $$$i$$$-й ячейки ($$$|x_i|, |y_i| \le 10^9$$$). Гарантируется, что пары $$$(x_i, y_i)$$$ уникальны, то есть что никакая ячейка не перечислена дважды.

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

В первой строке выведите целое число $$$k$$$ — количество ячеек, которые вы удаляете. В следующих $$$k$$$ строках перечислите координаты удаляемых ячеек в том же формате, что и во входных данных.

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

Система оценки

В этой задаче всего 43 теста, не считая примеров к условию. Все тесты оцениваются независимо. Если ваш ответ на определенный тест корректен, за этот тест вы получаете $$$$$$\mathtt{score} = \begin{cases} 0 & \text{если } \frac{j}{p} < \gamma \\ \mathtt{cost} \cdot \min\left(1, \frac{j}{p}\right) & \text{иначе} \end{cases}$$$$$$ баллов, где $$$\mathtt{cost}$$$ — стоимость теста, $$$p$$$ — количество ячеек, удаляемых в вашем ответе, $$$j$$$ — количество ячеек, удаляемых решением жюри, и $$$\gamma$$$ — нижняя граница на «оптимальность ответа».

Иными словами, если ваш ответ более чем в $$$\gamma^{-1}$$$ раз хуже ответа жюри, вы получаете $$$0$$$ баллов за этот тест. Иначе вы получаете долю от максимального числа баллов за тест, отражающую насколько оптимален ваш ответ в сравнении с ответом жюри.

ТестыБаллы $$$\mathtt{cost}$$$Граница $$$\gamma$$$Доп. ограничения
1 – 52$$$0$$$$$$n \leqslant 3$$$
6 – 103$$$0.5$$$$$$n \leqslant 18$$$
11 – 202$$$0.25$$$$$$n \leqslant 1000$$$, множество двусвязно
21 – 302$$$0.7$$$каждая ячейка множества имеет не более трех соседей
31 – 393$$$0.5$$$нет
40 – 435$$$1.0$$$нет

Примеры

Входные данные
3 0 0.0
1 0
0 1
1 1
Выходные данные
1
1 0
Входные данные
7 0 0.0
1 2
0 2
1 1
2 1
2 2
1 3
0 3
Выходные данные
1
1 2
Входные данные
12 0 0.0
1 0
3 -1
0 1
2 0
1 1
-1 3
1 2
3 1
2 2
1 3
4 2
3 3
Выходные данные
2
1 1
1 3

Примечание

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

Все ячейки множества выделены фиолетовым цветом. Красные круги соответствуют треугольным скоплениям. Первое из них образовано ячейками $$$(0, 1)$$$, $$$(1, 0)$$$ и $$$(1, 1)$$$; второе — ячейками $$$(1, 0)$$$, $$$(1, 1)$$$ и $$$(2, 0)$$$; и третье — $$$(1, 2)$$$, $$$(1, 3)$$$ и $$$(2, 2)$$$. Очевидно, что удаление одной ячейки не позволит избавиться от всех треугольных скоплений. А если удалить две, например, $$$(1, 1)$$$ и $$$(1, 3)$$$, треугольных скоплений не останется.