[POI2005] PUN-Points
题目描述
A set of grid points in a plane (points whose both cartesian coordinates are integers) which we shall refer to as the pattern, as well as a group of other sets of grid points on the plane are given. We would like to know which of the sets are similar to the pattern, i.e. which of them can be transformed by rotations, translations, reflections and dilations so that they are identical to the pattern. For instance: the set of points $\{(0,0),(2,0),(2,1)\}$ is similar to the set $\{(6,1),(6,5),(4,5)\}$, it is however not similar to the set $\{(4,0),(6,0),(5,-1)\}$.
TaskWrite a programme which:
reads from the standard input the description of the pattern and the family of the investigated sets of points,determines which of the investigated sets of points are similar to the pattern,writes the outcome to the standard output.
题目描述:
给出一个包含平面上格点的集合(格点的定义是xy坐标均为整数),我们将其称作“模式集合”。
接下来给出另外的几个包含平面上点的集合。我们想要考察后面给出的哪些集合和“模式集合”是“相似”的,即:该集合可以通过 旋转,平移,翻转,和缩放 使得该集合和“模式集合”完全相同。
例:{(0,0),(2,0),(2,1)}这个集合和{(6,1),(6,5),(4,5)}这个集合是相似的,但和{(4,0),(6,0),(5,-1)}这个集合是不相似的。
任务:
写一个程序,使得
能从标准输入读取“模式集合”和需要考察(是否相似)的集合,判断哪些集合和“模式集合”相似,并将结果输出到标准输出
输入格式:
标准输入的第一行有一个整数 k (1<=k<=25000),代表“模式集合”中的点数
接下来k行,每行两个数,用一个空格分隔,第i+1行的两个数分别代表“模式集合”中第i个点的x坐标和y坐标(-20000<=x,y<=20000)
“模式集合”中的点两两不同。
接下来一行一个整数n,代表有n个需要考察的集合
接下来有n个对需要考察的集合的描述:
每个描述的第一行包含一个整数l,代表该集合中的点数(1<=l<=25000)
接下来l行每行包含该集合中一个点的x坐标和y坐标,用一个空格分隔(-20000<=x,y<=20000,为整数)
包含在同一集合中的点两两不同。
输出格式:
你的程序应该向标准输出流输出n行,每行代表对于一个需要考察的集合的结果。
如果第i个需要考察的集合与“模式集合”相似,则第i行应包含单词TAK,即波兰语中的yes
否则第i行应包含单词NIE,即波兰语中的no
输入输出格式
输入格式
In the first line of the standard input there is a single integer $k$ ($1\le k\le 25\ 000$) - the number of points the pattern consists of. In the following $k$ lines there are pairs of integers, separated by single spaces. The $(i+1)$'st line contains the coordinates of $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, a single 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 which belong to the same set are pairwise different.
输出格式
Your programme 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 of the given sets of points is similar to the pattern, or the word NIE (i.e. no in Polish) if the set does not satisfy this condition.
输入输出样例
输入样例 #1
3
0 0
2 0
2 1
2
3
4 1
6 5
4 5
3
4 0
6 0
5 -1
输出样例 #1
TAK
NIE