推 willow02:感恩!! 03/17 18:51
※ 引述《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的Maximal Point就是解答..
整個演算法除了一開始的排序需要O(nlgn)之外，其餘部分跟Mergesort
類似，所以複雜度就是O(nlgn)。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50