切換
舊版
前往
大廳
主題

ZeroJudge - b182: 3. 矩形的內部與外部 解題心得

Not In My Back Yard | 2019-01-15 23:03:15 | 巴幣 0 | 人氣 129

題目連結:


題目大意:
給定兩正整數 m (1 < m < 31)、 n(1 < n < 10),代表有 m 個矩形和 n 個點。

接下來的 m 列輸入,每列有四個非負整數 x 、 y 、 x 、 y (皆不大於 40, 000) ,代表一矩形的左上角、右下角(或是左下角、右上角,且給定順序不固定)。

再接著的 n 列輸入,每列有兩整數 x 、 y ,代表某一個點的座標。對於每個給定的點,找出所以包含此點(在矩形的內部或是邊上)的矩形之面積和。



範例輸入:
4 3
0 0 5 5
3 3 1 1
14 15 20 7
5 8 10 5
5 5
2 4
15 1



範例輸出:
40
25
0



解題思維:
因為只會給矩形的對角頂點,而且不知會給左下角、右上角還是左上角、右下角,順序也不固定。

因此輸入進 x 、 y 、 x 、 y 時,我們可以先判斷誰左誰右(x 座標大的在右邊)。判斷誰左誰右之後,在判斷左邊和右邊的 y 座標的大小關係。如果左邊的點之 y 大於右邊的,則給定的兩點為左上角和右下角;反之為左下角、右上角。

知道了是哪兩個對角頂點後,就可以生出另外兩點的座標。再來輸入 x 、 y 後,判斷此點是否在矩形左上角的右下方、右上角的左下方、左下角的右上方以及右下角的左上方。如果都符合,即在矩形內,把此矩形的面積加進答案內。然後繼續判斷下一個矩形。

最後,輸出上面找出的矩陣的面積和即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作