시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|

1 초 | 128 MB | 105 | 33 | 13 | 19.697% |

VLSI circuits are too complex to design without CAD tools since the complexity of many VLSI circuits is in the order of millions of transistors today. In order to reduce the complexity of the design process for a VLSI circuit, the whole process is broken into several intermediate phases. Among them is a physical design phase. In the physical design phase, the basic components of the circuit are usually thought of as rectangular modules. The physical design phase itself consists of several steps. One of the steps, which is most crucial for the performance of the circuit, is a floorplan/placement step. Actual floorplan/placement problem in the VLSI circuit design is very complex. However, here, you are asked to deal with a simple version of the problem, in which each component of a VLSI circuit can be viewed as a rectangle in the plane.

A simple version of the floorplan/placement problem is to place n rectangles in the plane in axis-parallel orientation such that some given constraints are satisfied. Information about relative locations among rectangles is given as constraints. Relative location means that rectangle R_{i} (1 ≤ i ≤ n), should be placed either below (or above) rectangle R_{j} (1 ≤ j ≤ n), or to the left (or right) hand side of rectangle R_{j}. For each rectangle R_{i}, the coordinates of its lower left corner and its upper right corner are represented as (x_{i}^{ll}, y_{i}^{ll}) and (x_{i}^{ur}, y_{i}^{ur}), respectively. That rectangle R_{i} is located below rectangle R_{j} means y_{i}^{ur} ≤ y_{j}^{ll}. Similarly, that rectangle R_{i} is to the left of rectangle R_{j} means x_{i}^{ur} ≤ x_{j}^{ll}. Notice that each rectangle can be placed rotated by 90°. Figure 1 shows two example cases in which rectangle R_{1} is below rectangle R_{2}.

Figure 1. Two example cases to illustrate R_{1} is below R_{2}

The constraints regarding relative locations among the rectangles are represented as a binary tree called ‘slicing tree.’ A slicing tree represents how the plane is partitioned and which rectangle should be placed in each sub-region. Each internal node of the slicing tree is labeled as either Ⓗ or Ⓥ. Each external node of the slicing tree is labeled with a rectangle identification number i (1 ≤ i ≤ n). The label Ⓗ or Ⓥ for an internal node means that the sub-region on the plane is partitioned either by a horizontal line or by a vertical line. For example, if the slicing tree is as shown in Figure 2, it means that the plane is partitioned by a horizontal line and that rectangle R_{1} should be placed below rectangle R_{2}. Notice that both of the placements shown in Figure 1 meet the constraint shown in Figure 2.

Figure 2. An example of slicing tree for 2 rectangles

On the other hand, if the slicing tree is as shown in Figure 3, it means that the plane is partitioned by a vertical line and that rectangle R_{1} should be placed to the left hand of rectangle R_{2}.

Figure 3. Another example of slicing tree for 2 rectangles

If any internal node N_{k} in the slicing tree is labeled as Ⓗ, all the rectangles belonging to the left sub-tree rooted at N_{k} should be placed below any rectangles belonging to the right sub-tree rooted at N_{k}. Similarly, if any internal node N_{k} in the slicing tree is labeled as Ⓥ, all the rectangles belonging to the left sub-tree rooted at N_{k} should be placed to the left of any rectangle belonging to the right sub-tree rooted at N_{k}. For example, Figure 4 shows a slicing tree and two different corresponding placements.

Figure 4. A slicing tree and its two different corresponding placements

Let \(\boxed { R } \) denote the minimum rectangle which encloses all the rectangles when a placement is determined. Such enclosing rectangles corresponding to the placements shown in Figure 4 are shown in Figure 5 with dotted lines.

Figure 5. Minimum enclosing rectangles

Given information regarding a slicing tree and the rectangles’ dimensions, your program should determine the location for each rectangle such that the placement meets the given constraints and such that the area of the enclosing rectangle \(\boxed { R } \) is as small as possible. Notice that the area of the enclosing rectangle \(\boxed { R } \) can be affected by the orientation of each rectangle.

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n (1 ≤ n ≤ 1,000), where n is the number of rectangles. In the following n lines, dimensions of n rectangles are given, each line for each rectangle. The i–th (1 ≤ i ≤ n) line contains two integers, w and h (1 ≤ w,h ≤ 500), w for width and h for height of rectangle i. In the next line the information regarding a slicing tree is given. The information is represented as a list consisting of 2n - 1 items separated by spaces, which is obtained by traversing the slicing tree in post-order. Each item of the list is either a label for an internal node or for an external node. The label for an internal node is either H or V. The label for an external node is an integer i (1 ≤ i ≤ n), which is the rectangle identification number.

Your program is to write to standard output. Print exactly one line for each test case. For each test case, find a placement such that the given constraints regarding relative locations among rectangles are satisfied and the area of the enclosing rectangle \(\boxed { R } \) is as small as possible. Then print the area of the rectangle \(\boxed { R } \) for each test case. You can assume that the resulting area of \(\boxed { R } \) is less 10^{10} than for each test case.

2 5 1 5 4 2 3 3 1 3 5 4 2 1 V 3 5 H 4 V H 6 4 2 5 7 7 2 4 4 1 4 5 3 2 3 H 1 5 V 6 4 H V V

65 105