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

关于半平面算法S&I的问题

Posted by B007 at 2011-08-10 10:18:31 on Problem 1474
8
0 0
0 3
1 2
1 1
2 1
2 2
3 3
3 0

答案显然是 no, 但是按照算法流程徒手操作出来貌似却是yes
而且网上盛传的S&I算法模板有问题,1)是上述问题,本质问题。
2)是如果栈中有相邻两个不相交的半平面,就可能在计算直线交点的时候,无交点,
而模板中默认有交点,两条平行线求交点,就会发生除0的情况,即便这样,程序
依然无视它继续运行。例:
8
0 0 
0 2
1 2
1 1
2 1
2 2
3 2
3 0
令人惊讶的是本应该是WA&RE的代码却还可以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