題目連結:
給定兩正整數 m (1 < m < 31)、 n(1 < n < 10),代表有 m 個矩形和 n 個點。
接下來的 m 列輸入,每列有四個非負整數 x1 、 y1 、 x2 、 y2 (皆不大於 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
因為只會給矩形的對角頂點,而且不知會給左下角、右上角還是左上角、右下角,順序也不固定。
因此輸入進 x1 、 y1 、 x2 、 y2 時,我們可以先判斷誰左誰右(x 座標大的在右邊)。判斷誰左誰右之後,在判斷左邊和右邊的 y 座標的大小關係。如果左邊的點之 y 大於右邊的,則給定的兩點為左上角和右下角;反之為左下角、右上角。
知道了是哪兩個對角頂點後,就可以生出另外兩點的座標。再來輸入 x 、 y 後,判斷此點是否在矩形左上角的右下方、右上角的左下方、左下角的右上方以及右下角的左上方。如果都符合,即在矩形內,把此矩形的面積加進答案內。然後繼續判斷下一個矩形。
最後,輸出上面找出的矩陣的面積和即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。