UVA513 Window Frames
题目描述
### 翻译
#### 元素的图形用户界面
图形用户界面的元素包括按钮、文本框、滚动条、下拉菜单和可滚动列表框。这些控件被称为小部件。小部件的位置、分配的空间及其大小变化共同构成了窗口的几何结构。
#### 几何管理方案
一种几何管理方案使用特殊的矩形框架（frames）来包含和组合其他小部件。一个框架如果将其空间分配给其他框架，则称为父框架（parent），这些被分配的框架称为子框架（children）。没有父框架的框架称为根框架（root frame），其大小由用户指定（在输入数据中）。这个问题要求确定空间的分配以及放置在各种尺寸的根框架中的框架的位置。
框架中的空隙（cavity）是指不被子框架占用的空间。当创建一个新的子框架时，它会被分配在沿顶部或底部边缘的整个水平条（称为水平子框架）或沿右侧或左侧边缘的整个垂直条（称为垂直子框架）中。因此，创建一个新的子框架后，空隙会变得更小，但仍保持矩形。将子框架放置在父框架内的过程称为包装（packing）。子框架根据包装顺序放置在空隙中。
下图显示了一个父框架的子框架。首先在右边缘放置框架1，然后沿底边放置框架2，沿左边缘放置框架3，最后沿右边缘放置框架4。空隙显示为白色，包含可用于放置后续子框架的空间。
#### 包装框架的尺寸
每个框架覆盖一个像素的矩形网格。如果根框架覆盖c列和r行像素，则左上角的像素坐标为(0,0)，右下角的像素坐标为(c-1, r-1)。框架的位置由其左上角像素和右下角像素的坐标指定。
每个框架的最小尺寸由输入参数d和其子框架的最小尺寸决定。框架必须至少足够大以容纳其所有子框架。各框架的最小尺寸如下所示：
| Packing Side | Frame Type | Minimum Width | Minimum Height |
|--------------|------------|----------------------------------------|-----------------------------------------|
| Right or left| Vertical | Maximum of d and the width necessary for the frame’s children | Maximum of 1 and the height necessary for the frame’s children |
| Bottom or top| Horizontal | Maximum of 1 and the width necessary for the frame’s children | Maximum of d and the height necessary for the frame’s children |
当框架大于上述最小尺寸时，多余的内部空间会分配给其子框架和/或其空隙。每个框架都有一个扩展标志（输入参数），当设置时，表示垂直框架可以变宽或水平框架可以变高。例如，扩展标志设置为垂直框架时，分配的空间沿空隙顶部扩展，使框架变高。
#### 水平和垂直空间的分配
水平空间的分配如下：设x为父框架超过其最小宽度的水平像素数。若n为垂直子框架在父框架中具有扩展标志的数量，非零则按比例分配x像素。否则，增加空隙宽度。
类似地，垂直空间的分配也遵循相同的原则，水平子框架利用额外的垂直像素，垂直子框架不变，增加空隙高度。
示例说明了根框架放大后的效果。只有框架4、6和7设置了扩展标志，分配了多余的水平和垂直空间。
输入格式
```
M N
```
M为排除根框架的框架总数，N为不同根框架尺寸数（均为正整数）。接下来M行的格式为：
```
n p s d e
```
其中n为框架名称（正整数），p为父框架名称（0表示根框架），s为包装边的字符（L、R、T、B），d为最小尺寸（正整数），e为扩展标志（0或1）。
接下来N行的格式为：
```
c r
```
其中c为像素列数，r为根框架的像素行数（均为正整数）。
根框架不列出。子框架在其父框架之前不出现。按顺序打包子框架，结束以M和N均为0表示。
输出格式
按每个根列出其尺寸（行×列）和每个框架的名称及其左上角和右下角坐标。如果根框架尺寸太小，输出“is too small”。不同根尺寸的输出以破折号分隔。
#### 示例输入
```
7 1
1 0 R 50 0
2 0 R 10 0
3 0 L 40 0
4 0 R 20 1
5 0 T 30 0
6 5 R 20 0
7 5 L 10 1
1000 1000
2 2
1 0 R 100 1
2 0 T 30 1
100 50
200 100
0 0
```
#### 示例输出
```
Root Frame #1
------------------------------
Display: 1000 X 1000
Frame: 1 (950,0) (999,999)
Frame: 2 (0,990) (949,999)
Frame: 3 (0,0) (39,989)
Frame: 4 (70,0) (949,989)
Frame: 5 (40,0) (69,29)
Frame: 6 (50,0) (69,29)
Frame: 7 (40,0) (49,29)
------------------------------
Root Frame #2
------------------------------
Display: 100 X 50 is too small
------------------------------
Display: 200 X 100
Frame: 1 (1,0) (199,99)
Frame: 2 (0,0) (0,99)
------------------------------
```