|
|
| Show all threads Hide all threads Show all messages Hide all messages | | If you get WA, try this test too | BigPolandBro | 1065. Frontier | 23 Sep 2020 00:06 | 1 | 6 1
1 0
0 4
0 6
1 10
2 6
2 4
1 5
answer is 8 | | efficient idea | Cuac!++ | 1065. Frontier | 24 Apr 2018 00:12 | 3 | 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). | | Why I got wrong answer? Please help me! | Grebnov Ilya[ISPU] | 1065. Frontier | 30 Jan 2011 13:01 | 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 | | If you get WA, try this test case | Tiberiu Danet | 1065. Frontier | 20 Jul 2009 15:54 | 12 | 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 |
|
|
|
