Кевин (один из миньонов) увлекся рисованием на шестиугольных решетках. Шестиугольной решеткой называется решетка, разбивающая плоскость на равные правильные шестиугольники. Каждый шестиугольник однозначно соответствует паре целочисленных координат, где первая ось координат направлена строго вниз, а вторая — под углом $$$120^\circ$$$ к ней. Рисунок, изображающий решетку и систему координат, можно видеть ниже:
Две ячейки называются соседними, если их границы имеют общую сторону. Например, ячейки $$$(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 – 5 | 2 | $$$0$$$ | $$$n \leqslant 3$$$ |
6 – 10 | 3 | $$$0.5$$$ | $$$n \leqslant 18$$$ |
11 – 20 | 2 | $$$0.25$$$ | $$$n \leqslant 1000$$$, множество двусвязно |
21 – 30 | 2 | $$$0.7$$$ | каждая ячейка множества имеет не более трех соседей |
31 – 39 | 3 | $$$0.5$$$ | нет |
40 – 43 | 5 | $$$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
На рисунках ниже нарисовано множество из третьего примера к условию, а также отмечены все треугольные скопления, и какие ячейки следует удалить.