a074: Covering a Hole 覆蓋孔洞
標籤 : Comprehensive
通過比率 : 100% (4 人 / 4 人 ) (非即時)
評分方式 :
Tolerant

最近更新 : 2020-04-16 08:43

內容

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

  1. The number of the vertices of H, denoted by n, is a positive integer between 4 and 100.
  2. The x-coordinates and y-coordinates of vertices are integers between 0 and 1000.

湯姆在一家公司工作,該公司生產各種孔洞的蓋子,例如街道和水井的孔洞。 他遇到以下問題:給定一個孔洞H(該孔洞是一個僅具有90度或270度內角的多邊形),請找出可以完全蓋住H的最小矩形蓋子。在此問題中,H的坐標是由每個邊緣均為垂直或水平的坐標系統表示。覆蓋孔洞時,蓋子的每個邊緣在同一坐標系統中也應為垂直或水平。

考慮圖1中的示例。很容易看出,可以完全覆蓋H的最小矩形蓋子是大小為4 × 8的矩形。

 

圖1:矩型孔洞H

 

在此問題中,你被要求找出可以完全覆蓋H的最小矩形蓋子。例如,在圖1中,輸出為32。

 

特別定義:

  1. H的頂點數(用n表示)是4到100之間的正整數。
  2. 頂點的x坐標和y坐標是0到1000之間的整數。

 

輸入說明

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
測資資訊 :
記憶體限制 : 64 MB
隱藏 測資點#0 (50%): 1.0s , <1K
隱藏 測資點#1 (50%): 1.0s , <1M
提示 :
標籤:
Comprehensive
出處:
ITSA 教育部智慧創新跨域人才培育計畫 [編輯 :
zero_jason (zero_jason(MANAGER))
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」