作者jimmylin1024 (shibaLover)
看板Grad-ProbAsk
标题[理工] 台大电机103资结 对答案
时间Fri Dec 11 15:03:46 2020
板上没有找到完整的解答 所以自己写了一份参考
解答 希望大家可以讨论我的解答哪里有问题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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1607670228.A.562.html
1F：推 aa871220: 接受小弟一拜== 考那年一定死 晚点看看 12/11 16:13
2F：→ jimmylin1024: 自己补 第三题我的答案用sweep line + disjoint set 12/11 18:05
3F：→ jimmylin1024: 没办法处理重叠的大小circle ，因为只检查边有没有 12/11 18:05
4F：→ jimmylin1024: 相交。 这样的话就会多算closed region的数量（被包 12/11 18:05
5F：→ jimmylin1024: 含在大circle 里面的小circle自己会是一个set，如果 12/11 18:05
6F：→ jimmylin1024: 说没有其他circle 的边跟它碰到的话） 12/11 18:05
7F：→ jimmylin1024: 看有没有大神可以帮解这题QQ 12/11 18:05
8F：→ jimmylin1024: 第三题暴力法的话就直接每个circle都和其他人比较看 12/11 18:18
9F：→ jimmylin1024: 有没有重叠即可 是O(n^2) 12/11 18:18
11F：→ jimmylin1024: 感谢F大 我再研究看看 12/12 16:45
※ 编辑: jimmylin1024 (220.136.31.221 台湾), 12/12/2020 16:53:35