시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 0 | 0 | 0 | 0.000% |
Let us consider a set of polygons with sides parallel to the axes of the coordinate system. Such a set of polygons is called a system of contour lines, if it is possible to order all the polygons of the set, so that the first polygon contains the second polygon in its interior, the second polygon contains the third polygon in its interior etc.
Your task is to check, if a given set of polygons is a system of contour lines.
Write a program, which:
In the first line there is one natural number t (1 ≤ t ≤ 10), denoting the number of sets to processed. Following, there are t data sets. The first line of each data set contains one integer n (1 ≤ n ≤ 250), denoting the number of polygons in this set. Each of the next n lines contains one integer mi (4 ≤ mi ≤ 250, 1 ≤ i ≤ n), denoting the number of vertices of the i-th polygon, followed by mi pairs of integers xij and yij (0 ≤ xij, yij ≤ 200 000), separated with a single space. These pairs describe coordinates of consecutive vertices of the polygon. The sides of each polygon are parallel to the axes of the coordinate system. Furthermore, no two adjacent sides of any polygon are collinear. The perimeter of any polygon does not contain self-crossings.
The standard output should contain t lines. The k-th line should contain one word TAK
(i.e. yes in Polish), if the k-th set of polygons is a system of contour lines, NIE
(i.e. no in Polish) otherwise.
3 3 6 1 1 5 1 5 4 4 4 4 6 1 6 6 0 0 0 7 5 7 5 5 7 5 7 0 4 2 3 3 3 3 4 2 4 3 4 2 2 3 2 3 3 2 3 8 1 1 1 4 3 4 3 6 5 6 5 4 4 4 4 1 4 0 0 6 0 6 5 0 5 3 6 1 1 5 1 5 4 4 4 4 6 1 6 6 0 0 0 7 5 7 5 5 7 5 7 0 4 2 3 4 3 4 4 2 4
TAK NIE NIE
Contest > Algorithmic Engagements > PA 2006 7-3번