|
|
6 1 1 0 0 4 0 6 1 10 2 6 2 4 1 5 answer is 8 Hi!, i have gotten AC in this problem, but i have 0.093 secs, and im not well ranked on the best solutions table, i think the difficult part of this problem is to see which triangle have historical monuments inside, i did it with an O ( logM * M * N ) approach, do anybody have something better? i really would like to know how to get 0.015 secs or less. Thank you very much! Eric ( Cuac!++ ). Hi. I've got 0.015 secs. http://acm.timus.ru/status.aspx?author=34678&num=1065&refresh=noMy algo woks O(M*N + N^3). Here is my idea: i don't look which triangles contain historical monuments. i calculate which sequences of vertexes can we delete and what length we win if we do so. Then i find optimal way of selecting these sequences of vertexes. Do you need more details? Nope, it is at least O(M*N*log(N) + N^3), but with N~50 it is not noticeable. For each tower check how many towers can be skipped, that is for each possible skipping length check if there are monuments ccw to the chord: O(M*N^2), but can be O(M*N*log(N)) with binary search. For each length and each start calculate minimal perimeter on the way from start to start+length trying all intermediary towers: O(N^3). For each triple of towers that form a triangle, sum minimal perimeters and find the global minimum: O(N^3). [code was deleted] Edited by moderator 22.04.2004 00:58 5 2 8 9 0 -7 -8 -7 -8 1 -8 9 -4 -3 -1 -5 Your program outputs 37.20 but the answer is 51.78 Edited by author 13.05.2014 12:53 Try this test case: 4 0 0 0 0 3 3 0 2 0 The answer should be 8.61. You have to find a solution with non-zero area, but the original polygon's vertices may lie on the same line. Thanks for your test,I Aced my program Thanks very much. With the help of your TestData, I got ACed. Thank you very, very, very much! Thank you very, very, very much!!! what a good test!! thank you very much So many happy people there), but I still wa4 :P Will someone ACer put here correct answer for this test? 13 3 -5 3 -3 6 0 7 4 6 7 5 7 4 7 3 7 2 5 -3 4 -3 3 -3 -2 -3 -5 -2 3 3 5 0 -1 1 My prog says 30.20 Your answer is correct. Just a test: 4 2 0 2 1 0 0 -2 -1 0 0 1 0 -1 Answer: 8.94 If you want some test data, send E-mail to me, I can help you. Test for WA#4 6 1 -1 -1 -4 0 -1 1 1 1 4 0 1 -1 0 0 Answer 8.00 |
|
|