|
|
try longdouble XD I used longdouble instead of double and got AC Hi, I had wrong answer on test 9. Then I found an error and got the problem accepted. My test may be useful: 1000 1000 1 1 2 1 1 2 50 50 1 10 10 11 10 10 11 69.392 Eng. problem statement "namely its angle described in the second input line" "its angle" should be "its corner" or "its vertex" or "its point" I got Wrong Answer on 31-st test. Could someone tell me, what is the reason of this outcome? Or give me some testdata. So, there are precision problems. It it will help someone, here is the test: 100000000 100000000 0 0 1 0 1 1 0 99999999 1 0 99999998 100000000 99999998 100000000 99999999 Answer is -1. Edited by author 21.06.2008 14:14 Problem very complex I think that some trace of helpful tests very needed My first troubles was in test 4 and traing test 100 100 2 10 1 3 3 3 10 1 1 6 8 5 7 7 7 answer:-1 helped. Test 5- first for which N>1 I passed test 5,6 with help of 19 19 1 18 0 17 2 17 7 16 2 5 18 3 1 7 1 7 19 6 17 8 17 answer:36.895 for test 7 we must rewrite all geometric procedures in __int64 mode after that I jumped to test17 and have VA17 two test on the way: 10 10 1 1 0 0 2 0 7 7 2 6 9 4 0 6 0 7 7 8 7 8 6 answer=18.506 10 10 1 1 0 0 2 0 7 7 2 6 9 4 0 6 0 7 7 8 7 8 5 answer=-1 for tests 1-16 N>0, all triangles have square > 0, initial and final points are different. also:main idea works: optimal path goes between corners of forbidden zones which are convex 4-9 poligones(Minkowski sums) and Floid applicable what to do? my convex hull utilita uses inside double-value considirations. It is helpful to find pure int convex_hull utilita It became easy and I jumped to test 29. Interesting that I did not sense that tests 16 and 22 very tricky! In test 29 N==0, remove "заглушка" go forward! AC-0.89! Resume: problem is not most difficult in timus, thank to authorth, ships is not degenerated in all tests. How speed up: to use Dejkstra instead of Floid! Religion:Using float in geometric problems leeds often to Wa during a long time and may made us seek. Made Dejkstra!Two position up to 0.765AC. It doesn't the matter. Main reserve: to speed up subroutine: verify that segment with int ends intersects with convex poligon(it's inner part). Edited by author 10.03.2008 20:18 At last! Finally! AC - I've done it! My ultra-optimized program (15 kBytes) has passed all the tests (22 or more!) within 0.593 sec (maximal time on 8-th test with N=40). During almost a week I've been trying to solve it - and now success! I really think this problem is one of the best on Ural, and one of the several from thousands I really proud to solve - bright idea, need for strict optimization and very tricky tests (especially 16 and 22). Just try to solve it - and feel the power of your brain! Yes, this problem is REALLY superior! I was forced to use __int64-calculations to avoid error in precision, so 0.921 sec. There is 10 tasks in one! #1271 is the best on Timus! Edited by author 11.08.2004 05:43 You are a lol and an idiot! You used a dirty account... hm... i think you use a dirty account too... I started using a dirty account when i lost a lot of submits at a problem because one of the tests did not correspond with the problem statement (can't remember what problem, it was a long time ago). I solved all the problems though. There ain't nothing dirty 'bout that :) sory, maybe i wasn't polite :) But it's realy not interesting to use a dirty account... хорошо, но если атлаживать решения под грязными именами станут все? Кто выиграет? Речь идет о том, что если кто-то, где-то, что - то, неправильно сделал в решении, то он получает свое - штрафные попытки, а если кто-то все сделал правильно и быстрее, то он и теряет меньше. Кто мешает тебе(я ничего против тебя не имею :)) или кому-то еще сдать задачу сразу?! Это неписаное правило олимпиадчиков: не отаживать решение под "грязью". Ведь на тимусе нет или почти нет :) задач с некорректными тестами или с неправильным условием и т. п. ... Решаете сами, дело Ваше, но иногда стоит и не забывать про свою честь. Hey, please write english. Why do you attack him when you use dirty account too? hey! i am not attack him :) 1 account is for our schoollteam(all our teamplayers post solutions on this login) next account is mine :) Do you know russian? So, all of you have your own accounts, and you just send AC solution to schoolteam account... That is almost using dirty accounts.... No, I don't know russian, but since serbian is my mother language I almost understand what is written in russian. Test #4 was corrected, new tricky tests were added, hints were added to the problem statement. |
|
|