Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
关于这三点~In Reply To:我来说三点 Posted by:3xian at 2009-09-04 17:06:26 ^_^ 弱弱的猜想: 1.极角序凸包的那个bug只是之前没想到而已,知道这个bug后只要把求凸包的栈大小初始化为2就可以了,写法和以前基本一样 加两行代码或者预先处理一下? 2.要求纯顶点凸包,按1的方法求出来就行了 O(n)再扫一圈? 3.直接在纯顶点凸包上用RC多好 边旋转边判? 总结下这题用RC的方法: 1.用以上求纯顶点凸包的方法求得纯顶点凸包 2.在纯顶点凸包上用RC求最远点对 发此贴的目的: 1.说明下一些人写的RC(经过bug处理的除外)是不能处理非纯顶点凸包的(我写的就是) 2.说明下一些人写的极角序凸包(经过bug处理的除外)是不能得到纯顶点凸包的(我之前写的就是) 3.说明下一些Wa的程序的 RC 凸包 并没有写错,只要稍微处理一下bug就能AC了 猜想:discuss里很多人说用RC莫名其妙Wa 可能就是没意识到1,2点吧(反正我做这题好久都没意识到的) ^_^ 希望大家的RC都能顺利地AC哦~~~~~~~~ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator