※ 引述《FRAXIS (喔喔)》之銘言：
: ※ 引述《willow02 (柳聲)》之銘言：
: : 和第八題該怎麼做? 我手邊的答案似乎是用prune and search解的
: : 麻煩大家了
: : http://ezproxy.lib.ncu.edu.tw:8080/~arhui/cexamn/exam/EC02_98_01.pdf
: 先按照x軸排序
: 以x軸座標找出中點把問題切成等量的兩半，遞迴求解。
: 找出左半的Maximal Point和右半的Maximal Point（按照y軸排序）
: 因為左半的x佐標必小於右半的y座標，所以只要看y軸的大小就可以確定
: 有沒有被dominate，方法類似Mergesort的merge步驟。
這個步驟是怎麼判定有沒有被dominate
可以解釋的再詳細一點嗎?3Q
: 沒有被dominate的Maximal Point就是解答..
: 整個演算法除了一開始的排序需要O(nlgn)之外，其餘部分跟Mergesort
: 類似，所以複雜度就是O(nlgn)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.160.188.3