Tom works in a company that produces covers for all kinds of holes, such as holes on
streets and wells. He encounters a problem as follows: given a hole H which is a
polygon with interior angles of only 90 or 270 degrees, determine the smallest
rectangular cover that can completely cover H. In this problem, H is given in a
coordinate system such that each of its edges is either vertical or horizontal. When
covering a hole, each edge of the cover should also be either vertical or horizontal in
the same coordinate system.
Consider the example in Figure 1. It is easy to see that the smallest rectangular cover
that can completely cover H is a rectangle of size 4 × 8.
Figure 1: a rectangular hole H.
In this problem, you are asked to find the area of the smallest rectangular cover that can completely cover H. For example, in Figure 1, the output is 32.
Technical Specification
湯姆在一家公司工作,該公司生產各種孔洞的蓋子,例如街道和水井的孔洞。 他遇到以下問題:給定一個孔洞H(該孔洞是一個僅具有90度或270度內角的多邊形),請找出可以完全蓋住H的最小矩形蓋子。在此問題中,H的坐標是由每個邊緣均為垂直或水平的坐標系統表示。覆蓋孔洞時,蓋子的每個邊緣在同一坐標系統中也應為垂直或水平。
考慮圖1中的示例。很容易看出,可以完全覆蓋H的最小矩形蓋子是大小為4 × 8的矩形。
圖1:矩型孔洞H
在此問題中,你被要求找出可以完全覆蓋H的最小矩形蓋子。例如,在圖1中,輸出為32。
特別定義:
The first line is an integer t, 1 ≤ t ≤ 10, indicating the number of test cases.
Each test case starts with one line containing the number n, 4 ≤ n ≤ 100, of vertices of the hole H. Then, n lines follow, each of which includes two integers x and y, 0 ≤ x, y ≤ 1000, which are the coordinates of the vertices of the hole's polygon. In the order, they would be visited on a trip around the polygon.
第一行是整數t,1 ≤ t ≤ 10,表示測試案例的數量。每個測試案例都從包含孔洞H的頂點的數量n,4 ≤ n ≤ 100的一行開始。然後,跟隨n行,每行包含兩個整數x和y,0 ≤ x, y ≤ 1000,是孔洞多邊形的頂點的坐標,依照在多邊形周圍繞一圈的順序讀取它們。
For each test case, output the area of the smallest rectangular cover that can completely cover H in one line.
對於每個測試案例,輸出一行可以完全覆蓋H的最小矩形蓋子的面積。
2 10 10 1 10 2 8 2 8 5 7 5 7 2 5 2 5 4 2 4 2 1 4 2 1 5 1 5 4 2 4
32 9
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |