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

Re:为什么这题先求凸包，再暴力不行呢？不是凸上面的点很少吗？那个beauty contest可以这么搞的。

Posted by tasty at 2014-06-23 21:03:33 on Problem 1912 and last updated at 2014-06-23 21:06:08
In Reply To:为什么这题先求凸包，再暴力不行呢？不是凸上面的点很少吗？那个beauty contest可以这么搞的。 Posted by:yygy at 2014-06-23 09:55:21 
做题要考虑算法的最坏情况，给你一个10万个点的凸包 暴力不就挂了。平时练习的时候考虑全面点好。。

PS:这道题N*LOG(N)也不难，直接二分找凸包中极角最接近直线的两个点 判断是否在两侧就行了。。。
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