Задача №113713. Звёздное небо
Юный астроном Даниэль любит смотреть на неисследованные части звездного неба и выискивать созвездия.
Будем считать, что звёздное небо представляет собой плоскость, на которой находятся \(n\) звёзд, являющихся различными точками, при этом никакие три из этих точек не лежат на одной прямой. Даниэль считает созвездием любой набор из \(k\) различных звёзд, являющихся вершинами выпуклого \(k\)-угольника (который возможно содержит другие звёзды внутри себя).
Ночь уже на исходе, а Даниэлю очень хотелось бы найти новое созвездие! Помогите ему это сделать, или определите, что на этот раз его ждёт разочарование.
В первой строке содержатся два числа \(n\) и \(k\) (\(4 \le n \le 1000\), \(4 \le k \le \min(6, n)\)) — количество звёзд на небе и требуемый размер искомого созвездия.
Следующие \(n\) строк описывают координаты звёзд, \(i\)-я из этих строк содержит два целых числа \(x_i\) и \(y_i\) — координаты \(i\)-й звезды (\(-10^6 \le x_i, y_i \le 10^6\)).
Гарантируется, что никакие две звезды не находятся в одной точке и никакие три звезды не лежат на одной прямой.
В первой строке выведите "Yes" (без кавычек), если у Даниэля есть шансы найти подходящее созвездие и "No" (без кавычек), если искомого созвездия не существует.
Если созвездие нужного размера присутствует на небе, последующие \(k\) строк должны содержать координаты \(k\) звезд, образующих искомое созвездие в порядке обхода против часовой стрелки. Если подходящих ответов несколько, разрешается вывести любой из них.
4 4 0 0 1 1 0 4 4 0
No
5 4 0 0 7 0 3 1 4 1 4 4
Yes 0 0 7 0 4 1 3 1