[ACM] 460 [問題] 是否有判斷兩個長方形是否有覆蓋關係的

[bleed1979 (十三)]

感謝zerodevil版友提點，

僅需檢查假想的長方形的座標是否會產生 左>=右 或 下>=上 的情況

如果產生了是No Overlap，否則就輸出這個長方形。

最終版的code
http://code.google.com/p/uvaoj/source/browse/trunk/v4/460.cpp?spec=svn78&r=78


==

這個問題今天剛好碰到。

ACM UVa 460 Overlapping Rectangles
http://uva.onlinejudge.org/external/4/460.html

這題的目的是判斷兩個長方形是否有重疊。

如果沒有，直接輸出沒有。

如果有，要輸出區域的座標。

如果只有邊重疊，一樣是輸出沒有。


題目給定的測資是(左下角X，左下角Y)(右上角X，右上角Y)

和你原本的座標方法剛好相反方向，

不過再寫個巨集或函式換一下就有了。


我的解法是先產生一個假想的Overlap長方形，

再判斷這個長方形有沒有inside原本的兩個長方形(任一個皆可)


inside的部份應該不會太難(我是寫得還蠻複雜的)，

產生假想的Overlap長方形的部份，

就是左 = MAX(兩者左座標)，右 = MIN(兩者右座標)

如果左大於右，做SWAP。

多畫幾張圖就可以判斷彼此的關係。


詳細觀看程式碼就了解了。

http://code.google.com/p/uvaoj/source/browse/trunk/v4/460.cpp?spec=svn76&r=76

這個程式碼只能通過ACM UVa的測試。不一定100%正確。

僅供參考。


Bleed


※ 引述《lkklkksppspp (索爾)》之銘言：
: 各位高手您好
: 小弟目前要寫一個程式
: 要判斷前後抓到的兩個長方型區域是否有覆蓋或部分覆蓋
: 要對有覆蓋的地方做處理
: 小弟原本是使用每次都抓取左上與右下角的座標去判斷使否有覆蓋關係
: 但小弟的老師覺得這樣做沒有效率
: 給了小弟一個函數PTINREGION要小弟去研究
: 但小弟研究過後 發現該函數只是判斷某個點是否有在某個區域內
: 跟小弟要做的兩個長方型區域是否有覆蓋含意不太一樣
: 不知道是不是有高手會知道
: 兩個長方型區域之間的覆蓋關係
: 有這種函數可以用嗎?
: 若有的話 能提供該函數給小弟做參考嗎?
: 感激不盡

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.43.114.29
推 zerodevil:其實不用檢查inside
→ zerodevil:如果overlap長方形的 X左>=X右 or Y下>=Y上
→ zerodevil:就是No Overlap
→ bleed1979:感謝，我改一改上傳看看，等會回報。
→ bleed1979:1樓是對的，我會修改原文並註記。
※ 編輯: bleed1979       來自: 114.43.114.29        (06/26 20:19)