[理工] 台大電機103資結 對答案

[jimmylin1024 (shibaLover)]

板上沒有找到完整的解答 所以自己寫了一份參考
解答 希望大家可以討論我的解答哪裡有問題QQ （第三題最沒把握）
謝謝

第一題
題目：
https://imgur.com/Pffeq50
Ans :
https://i.imgur.com/irRlKzQ.jpg
https://i.imgur.com/PKFACvj.jpg

第二題
題目：
https://imgur.com/ScRsLxe
Ans :
https://i.imgur.com/LwfdONA.jpg

第三題
題目：
https://imgur.com/9NroCvq
Ans :
https://i.imgur.com/meyF6tr.jpg
https://i.imgur.com/Aa5irYP.jpg

第四題
題目：
https://imgur.com/ElLG6qY
Ans:
https://i.imgur.com/hOAebUy.jpg
https://i.imgur.com/7QfJntE.jpg
https://i.imgur.com/wecxqny.jpg
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.136.31.221 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1607670228.A.562.html
推 aa871220: 接受小弟一拜== 考那年一定死 晚點看看
→ jimmylin1024: 自己補 第三題我的答案用sweep line + disjoint set
→ jimmylin1024:  沒辦法處理重疊的大小circle ，因為只檢查邊有沒有
→ jimmylin1024: 相交。 這樣的話就會多算closed region的數量（被包
→ jimmylin1024: 含在大circle 裡面的小circle自己會是一個set，如果
→ jimmylin1024: 說沒有其他circle 的邊跟它碰到的話）
→ jimmylin1024: 看有沒有大神可以幫解這題QQ
→ jimmylin1024: 第三題暴力法的話就直接每個circle都和其他人比較看
→ jimmylin1024: 有沒有重疊即可 是O(n^2)
推 FRAXIS: https://en.wikipedia.org/wiki/Power_diagram
→ jimmylin1024: 感謝F大 我再研究看看
※ 編輯: jimmylin1024 (220.136.31.221 臺灣), 12/12/2020 16:53:35