Анімація вітряка#5130

Анімація вітряка

1 секунда

32 мегабайти

Складна

Анімація вітряка працює наступним чином:

Обирається двовимірний набір точок, жодні три з яких не лежать на одній прямій. Потім вибирається одна з точок як перший шарнір, і через цю точку проводиться пряма під певним початковим кутом. Анімація продовжується обертанням прямої проти годинникової стрілки навколо шарніра з постійною швидкістю. Коли пряма перетинає іншу точку, ця точка стає новим шарніром. У двох прикладах нижче, точки є $(- 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 \leq P \leq 1000$ 1 \le P \le 1000), яке є кількістю наборів даних, що слідують. Кожен набір даних повинен оброблятися однаково і незалежно.

Кожен набір даних складається з кількох рядків вхідних даних. Перший рядок кожного набору даних складається з чотирьох цілих чисел, розділених пробілами, за якими слідує одне число з плаваючою комою. Перше ціле число - це номер набору даних. Друге ціле число - це кількість точок $M$ , що слідують ( $3 \leq M \leq 20$ 3 \le M \le 20). Третє ціле число дає кількість $S$ шарнірних точок для виводу ( $3 \leq S \leq 20$ 3 \le S \le 20), а четверте ціле число дає індекс $I$ початкової точки ( $1 \leq I \leq M$ 1 \le I \le M). Число з плаваючою комою - це кут $A$ в градусах, на який початкова пряма обертається проти годинникової стрілки від горизонталі ( $0 \leq A \leq 180$ 0 \le A \le 180).

Наступні $M$ рядків у наборі даних містять координати точок набору. Кожен рядок складається з цілого числа, індексу точки $I$ , і двох чисел з плаваючою комою, координат $X$ та $Y$ точки відповідно.

Вихідні дані

Для кожного набору даних є один рядок вихідних даних. Він містить номер набору даних, за яким слідують $S$ індексів точок, розділених пробілами (виключаючи індекс початкової точки).

Приклади

Приклад 1