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:俺肯定俺的思路是对的。。。但是计算几何总是。。。说时容易做时难。。。就算给大家铺路吧

Posted by 2010kk2010 at 2011-03-31 23:36:35 on Problem 3304
In Reply To:俺肯定俺的思路是对的。。。但是计算几何总是。。。说时容易做时难。。。就算给大家铺路吧 Posted by:hanjialong at 2008-08-28 13:37:20
> 首先题中的要求等价于:存在一条直线l和所有的线段都相交。
> 证明:若存在一条直线l和所有线段相交,作一条直线m和l垂直,则m就是题中要求的直线,所有线段投影的一个公共点即为垂足。(l和每条线段的交点沿l投影到m上的垂足处)
> 反过来,若存在m,所有线段在m上的投影有公共点,则过这点垂直于m作直线l,l一定和所有线段相交。
> 
> 然后证存在l和所有线段相交等价于存在l过某两条线段的各一个端点且和所有线段相交。
> 充分性显然。必要性:若有l和所有线段相交,则可保持l和所有线段相交,左右平移l到和某一线段交于端点停止(“移不动了”)。然后绕这个交点旋转。也是转到“转不动了”(和另一线段交于其一个端点)为止。这样就找到了一个新的l。
> 
> 于是本题可归结为枚举两两线段的各一个端点,连一条直线,再判断剩下的线段是否都和这条直线有交点。
> 
> 如果哪位弟兄用我的方法AC了,或者发现我的方法是错的。给我站内!!!谢

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