|
|
Страница 1 I have WA, but I don't guess at the feature of this test. Does anyone have a problem with this test? Please comment your trick. You should be careful with the point (X, 0) that lies on line A + (B - A). The angle should be 0 there, but because of precision issues we all love this case can break ternary search. 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. Can the view angle has more than one maximum? 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. 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. Some new tests were added. Now your solutions got WA. But if you change constants in your ternary search you will get AC again. 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. In other words, is for input {A, B, C, D} result always equal to result for input {C, D, A, B} ? Yes, program with exchanging points' coordinates got AC. My programm search the greatest angle in x in [x1..x2] and got AC. But it's wrong. For example in test 0 3 1 1. PS Maybe i'm wrong Edited by author 13.01.2011 21:20 New tests were added. 84 authors lost AC. Edited by author 14.01.2011 02:29 Test 5 doesn't matter! When we formulate our solution mathematically rightly tests may be from 1 to 1000 and so on.You should your self determine where your house may take winds. I don't keep much hope on somebody looking in the discussion section for this problem with all that time passed after it's introduction but I would like to make the note that the view point should be with non-negative x coordinate. This is not clear from the problem statement. I still haven't passed the whole problem but adding this logic to my solution upgraded me from wa8 to wa9. Any other tricks someone has noticed? No, view point may have negative x coordinate, so there should be another reason for your advance from 8-th to 9-th test... I've compared my computer with my friend's accepted program. I found that his main algorithm is to find the maximal viewing angle between (x1,0) and (x2,0) using binary search. But I have a random data like this "-41 328 150 467" my program output 0.528878 {which meet the peak value at (173.423285,0) on the right side of (x2,0)} but his program output 0.527316 {which meet the peak value at (150,0)} Must the programmer view the Billboard bewteen (x1,0) and (x2,0)? If I misunderstood the description of this problem,please tell me the right one. Thank you very much. my AC program returns 0.528878. Thank you very much! I will check my solution more carefully. Try to check return values of trigonometric routines. For example, if you use atan2, make sure that if returned angle is negative you take an absolute value of it (not just add 2 * PI). Good luck! Mine was failing WA6 due to integer overflow -- remember to convert the data to float early :) Please, give me test#6 or answer for test#6,or tell me what could be a problem? Plz help i got WA on test #6. Can you give me some tests? Edited by author 13.05.2008 20:38 Can someone give me test number 5 and if possible write the solution? Thank you. EDIT: It also will be helpful if someone give me some tests with solutions and maybe some "tricky" test. EDIT2: Got AC. Edited by author 13.05.2008 03:18 Edited by author 15.05.2008 16:13 isti problem I don't know what is "bug" in your algorithm, but in my was that I made mistake while I was subtracting angles. I still do not know what is test case # 5. Do you find out what the problem was In the test #5 x1=x2. I had WA on this test because of wrong processing of this case. Edited by author 14.11.2008 22:29 Test 5 x1==x2 && y1>0 && y2>0 Solution: ternary search in extending interval :) Edited by author 21.03.2010 13:27 Can anybody tell me what is correct answer for this test, please? Test is: -1000 -1000 1000 1 Edited by author 12.05.2008 21:15 It's 3.141593 But I output this number, but it's WA? Why? How do you know that's the input data? My AC program outputs 3.141593... Sorry, i have just now noticed that this aren't correct input data... Can anybody give me correct datas, please? how can i see whats test #5? can anyone post me if he knows pls can anyone add any test examples, and the answers please it gives me wrong answer on test #5 The test set for the problem awhile does not contain case (x1=x2 and y1*y2=0). For this case answer is PI/2, while all other cases y1*y2<=0 have answer PI. The test case credits: Igor E. Tuphanov. Test 11 is the first test where x2 < x1. New tests have been added to problem 1436 Billboard. Solutions that were made after contest have been rejudged. Edited by author 03.03.2006 23:18 And what about the following case: 0 0 0 1 Or billboard's leg can't be on the road? If it can, we see: ang(0) = 0; lim[ang(x)] = pi/2 (x -> 0). So, there is no best angle. Yeah... It seems to me, i should output pi in this case. Yes, answer is PI, like in sample #4 Correct answer is PI/2 when x1=x2 and y1*y2=0. But there is no such test case awhile. Hi! My math solution is absolute correct! I know that test #6 is: -1000 -1000 1000 1 (Bin Search rulez :-)))) The correct answer on it is 3.141593 my program give this answer, but got WA. WHY??? It is impossible!!! Help me please... Bye! pi is indeed the correct answer for this case. have you tried output with moy digits after decimal point? there might be something wrong with your detection. i suggest you checking the value your trigonometric functions produce. Good Luck! Edited by author 03.03.2006 13:58 I happen to have a problem with the same test case... Would anyone be able to give some more information about - well, anything? ~edit~ Never mind, I got AC after moving the billboard so that the coordinates suit me :) Edited by author 06.05.2008 15:26 Edited by author 06.05.2008 15:27 So, what is correct answer for #6? Edited by author 12.05.2008 19:57 Edited by author 12.05.2008 19:57 Edited by author 12.05.2008 19:57 I don't understand what does 'the best viewing angle' mean. Let the billboard ends are at points A and B. Let the programmer is at point C (so, point C can move along the direct line). Then you may notice, that angle ACB is different as point C is moved. You have to find the maximal value of this angle. P.S. I almost sure that there must be precise English term for this notion, but I do not know it. Perhaps someone helps? 'Viewing angle' is just the precise English term for this. |
|
|