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:这么简单的题居然没人AC

Posted by JiaJunpeng at 2014-03-08 16:00:30 on Problem 3354
In Reply To:Re:这么简单的题居然没人AC Posted by:JiaJunpeng at 2014-03-08 13:47:14

> 确实 简单 ，直接 将线段朝两个方向平移一个无穷小量 再重新构图，所有的多边形就都完全不相交了，再直接dfs出最大环就行了。。O(m)搞定
> 
> 推荐一道加强版： 
> http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=278&page=show_problem&problem=3732
> 
> 需要配合扫描线算法
就是最外边的边界稍微蛋疼点。别的没什么意思

Followed by:

Post your reply here:

Home Page Go Back To top