Punkty
Limit pamięci: 32 MB
Dany jest zbiór punktów na płaszczyźnie o współrzędnych całkowitych,
który będziemy nazywać wzorem,
oraz zestaw innych zbiorów punktów na płaszczyźnie
(również o współrzędnych całkowitych).
Interesuje nas, które z podanych zestawów są podobne
do wzoru, tzn. czy można je tak przekształcić za pomocą
obrotów, przesunięć, symetrii osiowej i jednokładności, aby były
identyczne ze wzorem.
Przykładowo: zbiór punktów jest podobny
do zbioru , ale nie do zbioru
.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opisy: wzoru oraz zestawu
badanych zbiorów punktów,
-
wyznaczy, które z badanych zbiorów punktów są podobne
do wzoru,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba
całkowita () -
liczba punktów tworzących wzór.
W kolejnych wierszach zapisane są pary liczb całkowitych
pooddzielanych pojedynczymi odstępami.
W -ym wierszu są współrzędne
-tego punktu należącego do wzoru: i
().
Punkty tworzące wzór są (parami) różne.
W kolejnym wierszu zapisana jest liczba zbiorów do zbadania
().
Dalej następuje opisów zbiorów punktów.
Opis każdego zbioru rozpoczyna się od wiersza zawierającego jedną
liczbę całkowitą - liczbę punktów w danym zbiorze
().
Punkty te są opisane w kolejnych wierszach, po jednym w wierszu.
Opis punktu to dwie liczby całkowite oddzielone pojedynczym odstępem,
jego współrzędne i ().
Punkty tworzące jeden zbiór są parami różne.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy -
po jednym dla każdego badanego zbioru punktów.
Wiersz nr powinien zawierać słowo TAK,
gdy -ty z podanych zbiorów punktów jest podobny do
podanego wzoru, lub słowo NIE w przeciwnym przypadku.
Przykład
Dla danych wejściowych:
3
0 0
2 0
2 1
2
3
4 1
6 5
4 5
3
4 0
6 0
5 -1
poprawną odpowiedzią jest:
TAK
NIE
Autor zadania: Piotr Stańczyk.