Задача №114701. Тараканы общежития
Виталий — первокурсник престижного университета. Из-за коронавируса и новых ограничительных мер большинство студентов уезжают из общежития, но Виталий наоборот решил заселиться. К его удивлению, помимо немногочисленных однокурсников, в общежитии его ожидало полчище тараканов.
После непродолжительного подсчёта было выявлено, что всего в комнате Виталия без спроса проживают \(n\) тараканов. Также было замечено, что живут они лишь на полу. Для простоты скажем, что они представляют из себя целочисленные точки на плоскости. Тараканы крайне ленивые, поэтому они совсем не двигаются.
Виталий не переносит насекомых, тем более тараканов, поэтому он решил от них избавиться. Так как распаковать вещи времени особо не было, самым действенным подручным орудием оказался простой тапок. После некоторого числа тестов было выявлено, что если бить плоской стороной, тараканы спокойно переживают удар. Таким образом, надо бить боковой стороной, но в таком случае зона поражения представляет собой линию, то есть погибают только тараканы, находящиеся на этой прямой.
Виталий готов сделать только \(k\) ударов и если после этого получится так, что остался хотя бы один живой таракан, то студент в ужасе убежит. Помогите Виталию определить как ему следует бить.
В первой строке вводится \(t\) (\(1 \leq t \leq 50\)) — количество наборов входных данных.
Описание каждого набора входных данных начинается с двух целых чисел \(n\) и \(k\) (\(1 \leq n \leq 100\,000\), \(1 \leq k \leq 12\)) — количество тараканов на полу и число ударов, которое готов сделать Виталий, соответственно.
В следующих \(n\) строках вводится по два целых числа \(x_i\), \(y_i\) (\(|x|, |y| \leq 10^9\)) — коордианты \(i\)-го таракана. Гарантируется, что коордианты всех тараканов различны.
Наборы входных данных отделены пустой строкой.
Гарантируется, что сумма \(n\) в наборах входных данных не превосходит \(100\,000\).
Также гарантируется, что тест содержит не более одного набора входных данных с \(k \ge 11\).
Для каждого набора входных данных выведите « No » (без кавычек), если нельзя убить тараканов за \(k\) ударов.
Иначе выведите « Yes », а в следующей строке целое число \(m\) (\(1 \leq m \leq k\)) — количество ударов, которое необходимо сделать Виталию. В следующих \(m\) строках выведите по четыре целых числа \(x_{i, 1}\), \(y_{i, 1}\), \(x_{i, 2}\), \(y_{i, 2}\) (\(|x_{i, 1}|, |y_{i, 1}|, |x_{i, 2}|, |y_{i, 2}| \leq 10^9\)) — координаты двух точек, лежащих на прямой \(i\)-го удара.
Тесты к этой задаче состоят из четырнадцати групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
Обратите внимание, дополнительные ограничения на \(n\) не ограничивают сумму \(n\) по всем наборам входных данных.
| Дополнительные ограничения | ||||||
| Группа | Баллы | \(n\) | \(k\) | \(t\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 3 | \(n \leq 100\) | \(k \leq 1\) | – | – | |
| 2 | 3 | – | \(k \leq 1\) | – | 1 | |
| 3 | 6 | \(n \leq 100\) | \(k \leq 2\) | – | 1 | |
| 4 | 6 | – | \(k \leq 2\) | – | 1–3 | |
| 5 | 6 | \(n \leq 100\) | \(k \leq 4\) | – | 0, 1, 3 | |
| 6 | 6 | – | \(k \leq 4\) | – | 0–5 | |
| 7 | 10 | \(n \leq 100\) | \(k \leq 6\) | – | 0, 1, 3, 5 | |
| 8 | 10 | – | \(k \leq 6\) | – | 0–7 | |
| 9 | 9 | \(n \leq 100\) | \(k \leq 8\) | – | 0, 1, 3, 5, 7 | |
| 10 | 9 | – | \(k \leq 8\) | – | 0–9 | |
| 11 | 6 | \(n \leq 100\) | \(k \leq 10\) | – | 0, 1, 3, 5, 7, 9 | Offline-проверка. |
| 12 | 6 | – | \(k \leq 10\) | – | 0–11 | Offline-проверка. |
| 13 | 10 | \(n \leq 100\) | – | \(t = 1\) | 0, 1, 3, 5, 7, 9, 11 | Offline-проверка. |
| 14 | 10 | – | – | \(t = 1\) | 0–13 | Offline-проверка. |
2 12 4 1 2 -3 1 2 -2 2 -1 -1 0 2 -3 -1 4 -2 -1 0 4 -3 2 -3 -1 3 4 12 3 1 2 -3 1 2 -2 2 -1 -1 0 2 -3 -1 4 -2 -1 0 4 -3 2 -3 -1 3 4
Yes 4 -2 -1 -1 0 -3 -1 -3 1 2 -3 2 -2 -1 4 0 4 No