ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1436. Billboard

Weak tests again
Posted by I&K 14 Jan 2011 23:07
My solutions based on the wrong assumption that the view angle has only one maximum on abscissa axis (and with some tricks regarding to range of search or partition method in ternary search) pass all tests. Seems that more tests needed.
Re: Weak tests again
Posted by Sergey Lazarev (MSU Tashkent) 15 Jan 2011 00:13
Can the view angle has more than one maximum?
Re: Weak tests again
Posted by I&K 15 Jan 2011 12:36
Yes. It's zero at negative infinity, increases when moving to positive infinity and than decreases to zero at the point of intersection of the line containing billboard segment and the abscissa axis (assuming the segment itself doesn't intersect the axis). If we continue to move the view point to the positive infinity, the angle increases and decreases again.
Re: Weak tests again
Posted by Sergey Lazarev (MSU Tashkent) 15 Jan 2011 13:49
Now I understand what you meen. I searched maximum on the segment between point of intersection of board with abscissa axis and positive or negative infinity. I considered only this segment and was surprised that there can be more than one maximum on it.
Re: Weak tests again
Posted by Sandro (USU) 15 Jan 2011 14:31
Some new tests were added. Now your solutions got WA. But if you change constants in your ternary search you will get AC again.
Re: Weak tests again
Posted by Sergey Lazarev (MSU Tashkent) 15 Jan 2011 14:43
You are right. I've changed "infinity" from 10^6 to 10^4 and got AC. Can you explain why? It's the secont time I decreased segment for search and got AC.