P3418 [POI 2005] PUN-Points

# Description A set of grid points in the plane (points whose Cartesian coordinates are both integers), called the pattern, is given, as well as several other sets of grid points. We want to determine which of these sets are similar to the pattern, i.e., which can be transformed by rotations, translations, reflections, and dilations so that they become identical to the pattern. For example, the set of points {(0, 0), (2, 0), (2, 1)} is similar to the set {(6, 1), (6, 5), (4, 5)}, but it is not similar to the set {(4, 0), (6, 0), (5, −1)}. Write a program that: - reads the description of the pattern and the family of candidate sets of points from standard input, - determines which of the candidate sets of points are similar to the pattern, - writes the results to standard output.

A set of grid points in the plane (points whose Cartesian coordinates are both integers), called the pattern, is given, as well as several other sets of grid points. We want to determine which of these sets are similar to the pattern, i.e., which can be transformed by rotations, translations, reflections, and dilations so that they become identical to the pattern. For example, the set of points {(0, 0), (2, 0), (2, 1)} is similar to the set {(6, 1), (6, 5), (4, 5)}, but it is not similar to the set {(4, 0), (6, 0), (5, −1)}. Write a program that: - reads the description of the pattern and the family of candidate sets of points from standard input, - determines which of the candidate sets of points are similar to the pattern, - writes the results to standard output. # Description

In the first line of the standard input there is a single integer $k$ ($1\le k\le 25\ 000$) — the number of points in the pattern. In the following $k$ lines there are pairs of integers, separated by single spaces. The $(i+1)$-st line contains the coordinates of the $i$-th point belonging to the pattern: $x_{i}$ and $y_{i}$ ($-20\ 000\le x_{i},y_{i} \le 20\ 000$). The points forming the pattern are pairwise different. In the next line there is the number of sets to be investigated: $n$ ($1\le n\le 20$). Next, there are $n$ descriptions of these sets. The description of each set begins with a line containing a single integer $l$ — the number of points belonging to that particular set ($1\le l\le 25\ 000$). These points are described in the following lines, one point per line. The description of a point consists of two integers separated by a single space — its coordinates $x$ and $y$ ($-20\ 000\le x,y\le 20\ 000$). The points within the same set are pairwise different.

Your program should write to the standard output $n$ lines — one for each of the investigated sets of points. The $i$-th line should contain the word TAK (i.e., yes in Polish) if the $i$-th set of points is similar to the pattern, or the word NIE (i.e., no in Polish) if it is not.

Translated by ChatGPT 5