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:11:36 on Problem 1912
In Reply To:Re:为什么这题先求凸包,再暴力不行呢?不是凸上面的点很少吗?那个beauty contest可以这么搞的。 Posted by:tasty at 2014-06-23 21:03:33
> 做题要考虑算法的最坏情况,给你一个10万个点的凸包 暴力不就挂了。平时练习的时候考虑全面点好。。
> 
> PS:这道题N*LOG(N)也不难,直接二分找凸包中极角最接近直线的两个点 判断是否在两侧就行了。。。

推荐一道复杂一些的题目:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=66&page=show_problem&problem=3140

UVA不卡 set 代码也比较简单

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