Анимация Ветряной Мельницы
Анимация ветряной мельницы работает следующим образом:
Выбирается двумерный набор точек, ни три из которых не лежат на одной прямой. Затем выбирается одна из точек в качестве первой опорной точки, и через неё проводится прямая под некоторым начальным углом. Анимация продолжается, вращая прямую против часовой стрелки вокруг опорной точки с постоянной скоростью. Когда прямая касается другой точки, эта точка становится новой опорной точкой. В двух примерах ниже точки: (-1, 1), (1, 1), (0, 0), (-1, -2) и (1, -2).
Пример 1
В Примере 1 начальная точка - точка 1, и прямая начинается с поворота на 45 градусов от горизонтали. Когда прямая поворачивается до 90 градусов, точка 4 становится новой опорной точкой. Затем точка 5 становится новой опорной точкой, затем точка 2, затем точка 1.
Пример 2
В Примере 2 начальная точка - точка 3, и прямая начинается горизонтально. На 45 градусах точка 2 становится опорной, затем примерно на 56 градусах точка 4 становится опорной. Примерно на 63 градусах точка 3 снова становится опорной, затем точка 5, точка 1 и возвращается к 3, как в начале.
Напишите программу, которая принимает на вход точки набора, начальную точку и начальный угол линии и выводит последовательность опорных точек.
Входные данные
Первая строка ввода содержит одно целое число P, (1 ≤ P ≤ 1000), которое является количеством наборов данных, следующих за ним. Каждый набор данных должен обрабатываться одинаково и независимо.
Каждый набор данных состоит из нескольких строк ввода. Первая строка каждого набора данных состоит из четырех целых чисел, разделенных пробелами, за которыми следует одно число с плавающей запятой. Первое целое число - номер набора данных. Второе целое число - количество точек M, которые следуют (3 ≤ M ≤ 20). Третье целое число дает количество, S, опорных точек для вывода (3 ≤ S ≤ 20), а четвертое целое число дает индекс, I, начальной точки (1 ≤ I ≤ M). Число с плавающей запятой - это угол, A, в градусах, на который начальная линия повернута против часовой стрелки от горизонтали (0 ≤ A ≤ 180).
Оставшиеся M строк в наборе данных содержат координаты точек набора. Каждая строка состоит из целого числа, индекса точки, I, и двух чисел с плавающей запятой, координат X и Y точки соответственно.
Выходные данные
Для каждого набора данных выводится одна строка. Она содержит номер набора данных, за которым следуют S индексов точек, разделенных пробелами (исключая индекс начальной точки).