[理工] 台大电机103资结 对答案

楼主: jimmylin1024 (wiseman)   2020-12-11 15:03:46
板上没有找到完整的解答 所以自己写了一份参考
解答 希望大家可以讨论我的解答哪里有问题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
作者: aa871220 (TMVP_Yueko)   2020-12-11 16:13:00
接受小弟一拜== 考那年一定死 晚点看看
楼主: jimmylin1024 (wiseman)   2020-12-11 18:05:00
自己补 第三题我的答案用sweep line + disjoint set没办法处理重叠的大小circle ,因为只检查边有没有相交。 这样的话就会多算closed region的数量(被包含在大circle 里面的小circle自己会是一个set,如果说没有其他circle 的边跟它碰到的话)看有没有大神可以帮解这题QQ第三题暴力法的话就直接每个circle都和其他人比较看有没有重叠即可 是O(n^2)
作者: FRAXIS (喔喔)   2020-12-11 22:40:00
楼主: jimmylin1024 (wiseman)   2020-12-12 16:45:00
感谢F大 我再研究看看

Links booklink

Contact Us: admin [ a t ] ucptt.com