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 3xian at 2009-09-04 17:06:26 on Problem 2187
In Reply To:本题submit n次(n>=50) 后关于凸包与RC的体会 Posted by:alpc56 at 2009-09-04 09:18:45 
1. 极角排序求凸包的情况下，预先找出第一条边最远的点就可以避免你所谓的bug了吧。两行代码就够。

2. 一个有多点共线的凸包变成纯顶点凸包，O(n)扫一圈就可以完成。

3. 在一个有多点共线的凸包上用RC，需要判断哪些点不是顶点，这个可以像上一条所说O(n)预处理，也可以边旋转边判，每次用叉积O(1)判。
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