Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод ![Копировать номер copy](/images/simple/b_copy.png)
Послать решение Blockly Посылки Темы Где Обсудить (0)
Imagine a collection of two-dimensional rectangular blocks whose sides are perfectly horizontal
or vertical, pushed downward (in the negative `y`-direction) by gravity. Blocks resting on
the `x`-axis or firmly atop another block are well-supported, and resist tumbling downward. In this
problem, we are given the positions of a collection of blocks and determine which blocks are supported
and which are not supported. In the following example, blocks 2, 3, 5 and 6 are supported,
block 4 is not supported, and block 1 is not supported (but would be if moved slightly left or right).
Let `a` and `b` be blocks. We define `"top"(b)` and `"bottom"(b)` to be the `y`-coordinates of the bottom
edge and top edge of `b`, and define `"left"(b)`, `"center"(b)` and `"right"(b)` to be the `x`-coordinates of the
left edge, vertical center and right edge of `b`. We define
`a` left-supports `b` if `"bottom"(b)\ =\ "top"(a)` and `"left"(b)\ <\ "right"(a)` and `"center"(b)\ >\ "left"(a)`.
`a` right-supports `b` if `"bottom"(b)\ =\ "top"(a)` and `"right"(b)\ >\ "left"(a)` and `"center"(b)\ <\ "right"(a)`.
`b` is supported if `"bottom"(b)\ =\ 0` or
`∃a_l,\ a_r` : [`a_l` is supported and `a_r` is supported and
`a_l` left-supports `b` and `a_r` right-supports `b`].
Input Format
Each line of input describes a block `b` and contains non-negative integers `x,\ y` and positive
integers `w,\ h` separated by white space. `(x,\ y)` is the coordinate of the bottom left corner, `w` is
the width, and `h` is the height of block `b`. Blocks on successive lines are implicitly numbered
1, 2, 3, … You may assume that no two blocks in the input overlap.
Output Format
For each block described in the input, output a line giving the block number and indicating
whether or not it is supported, as shown in the output sample.
Sample Input
10 30 20 10
30 20 10 10
10 20 10 10
70 10 20 10
10 10 30 10
20 0 10 10
Sample Output
block 1 is not supported
block 2 is supported
block 3 is supported
block 4 is not supported
block 5 is supported
block 6 is supported
Source: California State Polytechnic University Programming Contest, Fall 2008