Detail of message

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

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:

好的，谢谢了。 (164) yygy 2014-06-23 21:57:32
我用类似于旋转卡壳的方法AC了。 (164) yygy 2014-06-24 14:38:45
- Re:我用类似于旋转卡壳的方法AC了。 (22) tasty 2014-06-24 16:35:53

Post your reply here:

Home Page Go Back To top