Feedback | | If you notice incorrect translations in Contester, please let author know.
|
|
Time limit 4000/6000/6000/6000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Дмитрий Шевченко, ВлГУ.
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
|
Для отправки решений необходимо выполнить вход.
|