題目連結
題意:
大意是給定一個長方形的長與寬
還有若干個小長方形(座標)
求原長方形內未包含在小長方形的面積大小
每組測資由3個數字為一行開頭
分別為W, H, N，W, H代表長方形的寬, 高
N為 後面還有 N 行測資，代表 N 個小長方形
每行分別有4個數字，為小長方形的對角線座標
舉例而言，有一組測資為:
4 3 1
1 2 4 3
表示有個4 * 3長方形
與一個對角座標為(1, 2), (4, 3)的小長方形(下圖紅框處為對角座標)
則剩餘面積為 4
解法:
根據大長方形的寬, 高建陣列
走訪每個小長方形佔到的面積做註記(如圖上綠色部分)
最後統計陣列內還沒註記的總和即可
要注意小長方形測資並沒有保證前者的座標會小於後者
也就是不一定為左下-右上的座標對
如上圖，也可能是(1, 3), (4, 2)(指的是相同小長方形)
不過，不論是何者，我們的目標是該綠色部分都要註記即可
迴圈部分可以這樣寫:
for (int i = Math.min(a1, b1); i <= Math.max(a1, b1); i++)
for (int j = Math.min(a2, b2); j <= Math.max(a2, b2); j++)
(a1, a2) (b1, b2)分別為2個對角座標測資
程式(Java):
題意:
大意是給定一個長方形的長與寬
還有若干個小長方形(座標)
求原長方形內未包含在小長方形的面積大小
每組測資由3個數字為一行開頭
分別為W, H, N，W, H代表長方形的寬, 高
N為 後面還有 N 行測資，代表 N 個小長方形
每行分別有4個數字，為小長方形的對角線座標
舉例而言，有一組測資為:
4 3 1
1 2 4 3
表示有個4 * 3長方形
與一個對角座標為(1, 2), (4, 3)的小長方形(下圖紅框處為對角座標)
則剩餘面積為 4
解法:
根據大長方形的寬, 高建陣列
走訪每個小長方形佔到的面積做註記(如圖上綠色部分)
最後統計陣列內還沒註記的總和即可
要注意小長方形測資並沒有保證前者的座標會小於後者
也就是不一定為左下-右上的座標對
如上圖，也可能是(1, 3), (4, 2)(指的是相同小長方形)
不過，不論是何者，我們的目標是該綠色部分都要註記即可
迴圈部分可以這樣寫:
for (int i = Math.min(a1, b1); i <= Math.max(a1, b1); i++)
for (int j = Math.min(a2, b2); j <= Math.max(a2, b2); j++)
(a1, a2) (b1, b2)分別為2個對角座標測資
程式(Java):
留言
張貼留言