SGU 512. Friendly Points

给你N个点,求所有这样的点对:它们构成的四边形中没有其它点。。
额。。只有25个人AC。。但我发现并不是很难。。至少没有其它几道那么变态。。
我的想法是分治算法,把所有点分成左右两份的话可以做到在NLogN的时间统计跨越两边的点对。。然后分治一下。。就是NLogN^2了。。。
Code:
www.ideone.com/NwuV9

4 thoughts on “SGU 512. Friendly Points

  1. 回复lhm_m:额。。。这类题目的话我觉得把各种条件都仔细的考虑考虑应该就能得出算法了吧。。还有就是多积累点感觉之类的。。。。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>