Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

关于这三点~

Posted by alpc56 at 2009-09-08 13:07:09 on Problem 2187 and last updated at 2009-09-08 13:20:04
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator