ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2009 > задача:


A. Tetris 3D

Задачи сборника

• A. Tetris 3D
• B. Knights of the Rook
• C. Meat store
• D. Many-coloured roads
• E. Kovrov
• F. Interesting permutations
• G. What about judges?
• H. Triangles
• I. ATM

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 4000/6000/6000/6000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Дмитрий Шевченко, ВлГУ.

Undoubtedly, Tetris is the best-known computer game in history. Many programmers tried to write their own versions of this game. Now you are given such an opportunity. We shall consider an extended version of this game - 3D Tetris. Imagine an infinite plane consisting of 1x1 cells. Figures fall from the sky in direction perpendicular to the plane. Figures can be rotated about the axis that is passing through the center of the figure and is perpendicular to the plane. You have to handle N commands that define the sequence of figures falling from the sky. Figures consist of 1x1x1 cubes. Figures fall in consecutive order according to the order of commands. Commands define coordinates of figure center, dimension of figure's parts, and rotation angles. There are 4 figures and corresponding commands:
  • TRIMINO x y n angle - defines the figure shown in picture 1.a. x, y are coordinates of the left lower corner of central cube (marked with black). n is the number of cubes for the main part of figure (watch picture for clarification). angle is the angle of rotation about the axis Z that is perpenicular to the plane. Angle can take on 4 values: 0, 90, 180, 270. The central cube does not change it's position after rotation (this is true for all figures), and the remaining cubes change it as shown in picture 1.a. For this kind of figure n will always be odd.
  • STICK x y n angle - defines the figure shown in picture 1.b. x, y, n have the same meaning as for previous figure, and angle can take on only 2 values: 0, 90. Cubes disposition after rotation is shown in picture 1.b. For this kind of figure n will always be odd.
  • GMINO x y n m angle - defines the figure shown in picture 1.c. x, y, angle have the same meaning as for previous figures. n and m are amounts of cubes for two parts of figure, as shown in picture 1.c. Note that figure dimensions do not change after rotation (this is true for all figures). In inital position (rotation by 0) number of cubes for horizontal part is n, and after rotation by 270 number of cubes in horizontal part is m.
  • STRANGEMINO x y n m angle - defines the figure shown in picture 1.d. x, y, angle have the same meaning as for previous figures. n and m are amounts of cubes for two parts of figure, as shown in picture 1.d.

After the fall the figure is located either on the plane or on another figure that it overlaps (maybe partially). Two figures overlap if they have at least one common cell on the plane. See picture 2 for clarification (overlapping cells are marked with gray). The total area of coverage is 14. Figures for picture 2 are generated by the following sequence of commands:

STICK 1 1 7 0
STICK 1 1 5 90
TRIMINO 4 2 3 180

Note that the order of commands is not important for us - any permutation of these commands will give the same result, from the point of view, perpendicular to the plane. Your goal is to find the total area of coverage. The cell is covered if there is at least one figure that includes the cube, that has the same coordinates as the cell, otherwise the cell is not covered (see picture 2 for clarification).

Input
The first line contains a single integer number N (1 ≤ N ≤ 2500). The following N lines contain commands, 1 command per line. Coordinates x, y can take on values from 1 to 25000 inclusive. m, n can take on values from 1 to 20000 inclusive.
Output
Output a single number - the total area of coverage.

Input 1 Output 1
1
TRIMINO 3 3 3 90
4
Input 2 Output 2
3
TRIMINO 3 3 3 90
STICK 100 100 5 0
STICK 100 100 5 90
13

Для отправки решений необходимо выполнить вход.

www.contester.ru