| Show all threads Hide all threads Show all messages Hide all messages |
| To admin | zhzqkkk | 1520. Empire Strikes Back | 16 Apr 2013 11:28 | 2 |
76 85
46 -22
4 15
-10 14
-12 7
-14 20
17 42
11 15
10 -10
60 15
18 -10
43 -51
27 22
-50 -32
-60 -11
-3 -29
-65 -13
-10 2
37 -7
9 -37
-39 42
80 -28
55 -41
-7 -77
-11 17
-6 -54
-55 -48
8 -58
-17 -52
-42 -8
26 -4
24 -13
29 41
-52 14
12 17
55 12
-50 43
27 -8
-33 -78
-42 -2
2 -71
-39 -6
52 -5
-25 62
-51 -2
-19 45
10 12
3 47
-61 37
13 -41
-7 -12
-7 -25
12 15
44 5
-47 -8
-3 -17
-12 -60
-2 28
37 -5
29 -7
-59 61
-17 50
-42 -19
26 51
-10 11
10 5
-1 31
-50 -23
7 -35
29 -47
-5 21
-69 11
13 -17
26 3
13 58
-40 30
-20 -12
please add this test
i found many AC program can't pass it.(they use Simulated Annealing) 58 88
40 -15
16 -18
-35 -53
-26 10
10 -64
-19 33
25 48
75 6
12 -65
29 31
-1 57
30 12
27 17
44 -11
24 -2
16 -25
21 -4
-57 24
51 25
26 20
-12 -27
23 -29
-22 6
13 -4
-11 -57
-18 17
-32 -22
-70 -17
-31 22
-47 69
-53 -64
-23 20
33 10
-13 -8
11 -25
-5 68
73 23
49 -15
68 -31
-33 -56
6 36
-13 -51
0 79
55 36
24 -1
54 -13
-21 -16
16 40
-38 11
15 3
20 -2
18 10
-16 27
-41 23
48 -24
35 -39
-61 10
-51 -14
also a good test
at last ,sorry for my poor english |
| WA5...I have no idea about it.Can somebody give me any useful tests? | Moya | 1520. Empire Strikes Back | 13 Jul 2011 09:25 | 2 |
It's my fault...
maybe 3 4 1 0 1 0 0 0 is a useful test.The right answer should be 4. |
| horrible | cherudim | 1520. Empire Strikes Back | 7 Nov 2010 18:48 | 1 |
|
| ignore it.. | shangjingbo | 1520. Empire Strikes Back | 22 Aug 2009 13:31 | 1 |
ignore it..just my mistake
Edited by author 22.08.2009 13:35 |
| WA#12..need help! | shangjingbo | 1520. Empire Strikes Back | 22 Aug 2009 06:53 | 1 |
Is it a precision problem?
who can give me some useful tests? |
| how to | nttjuvwamsncc | 1520. Empire Strikes Back | 30 Aug 2008 05:41 | 3 |
how to nttjuvwamsncc 14 Feb 2007 14:35 I think that enough for each circle-boundary to be
covered by others circles
or we have covering problem of arc by given set of arcs.
Have Ac based on this idea.
1504 ac with the same idea but
many hard work with eps.
Main difficult moment:
ends of arcs computed with help of arcos
have error with respect to exact values and may be
greater or smaller of them , but exact values of boundaries of intervals lies in distance eps=1.e-16 from computed values.
Edited by author 22.03.2008 17:50 It's Vorony diagrams problem. Of course, you may solve it via covering all arcs of all circles or even try binary search on radius.
2svr: as for comparing arcs - why do you need angles? Just keep x/y pairs defining direction and compare these pairs for <, =, > of angles they define. One of easy easy ways to do that:
y>0 || y==0 && x>0 - 1st part [0;pi)
y<0 || y==0 && x<0 - 2nd part [pi;2pi)
if 2 vectors belong to different parts, you alredy know which angle is smaller. If not, check sign of their cross product. |
| WA4. Help. Is there some spesial test ? [-] | Chmel_Tolstiy | 1520. Empire Strikes Back | 27 Jun 2007 17:47 | 3 |
The only tricky test I see here is N = 1 |
| Can you give me a hint on how to solve this? | Hao Hu (Ikki @ Nanjing University) | 1520. Empire Strikes Back | 14 Feb 2007 14:35 | 31 |
as the title
thanks in advance! Diagram of Voronoy, of course. Well well, the second problem on Timus that should be solved with diagram of Voronoy Well well, the second problem on Timus that should be solved with diagram of Voronoy This problem can be easily solved WITHOUT Voronoi's diagram.
I didn't write 1504 yet, but it also doesn't require such complicated methods. I got AC used diagram of voronoi.
Kit, please send me your program - efrcom@inbox.ru
It's very interesting for me, how solved it without voronoi's diagram.
I was not talking about 1504. I was talking about 1369 - the Cockroaches problem. Originally it was possible to solve the task with quadtree. But after new tests added to the task quadtree does not work. Therefore a more sophisticated structure is required. It's not clear. The plants are guaranteed to have integer coordinates. Is that true for Saddam too? If so, it's might be a simple binary search No, it is said that Sassam is somewhere in the circle - not required to be at an integer coordinate. (in fact he is somewhere else but... that's the problem statement - not up to date).
-- it would be good to post such question in other topics for the future He might be anywhere within the circle.
P.S. It is a pity Saddam III has been hang alone. I wonder when George II will follow him ;) To Kit:
I thought it can be solved without Voronoi's diagram, too. But I got Wrong Answer here. Could you send your solution to gaoyihan@gmail.com? I want to check my program. you can only give me the exe-file.
Edited by author 11.01.2007 16:24 I think it's binary search + Monte-Carlo. Is such approach correct?
Edited by author 11.01.2007 18:16 Why Monte-Carlo? I think, you'll get WA, because answer should be very accurate. Use binary search and bruteforce - O(N^3*logN), AC in ~ 0.25 secs. I think it's like this. The problem is how to define if for the given radius r the original circle is completely covered? (I don't think that there is a straight formula for 300 points). Therefore I just generate 50 points randomly and for each check does it belong to one of the inner circles or not. If there is a point that does not belong to any of the inner circle, the radius is not big enough, otherwise it's big enough. The binary search is obvious. How do you check the coverage with bruteforce? Any hint or algo? If you drop only 50 points, you'll not detect many little "white spaces" (when, for example, current radius 1e-3 less, than optimal. Obviously, such a solution will get WA.
How to check coverage with bruteforce? Intersect any two circles and consider epsilon neighborhood of their common points... Thanks a lot. But perhaps if I increase the number of random points (for each check a separate set of points), I'll get AC (if not from the first time, than from the second thanks to the random :) To my mind, it's practically impossible. You should check (1000/1e-5)^2 ~ 10^16 points on every step of binsearch to catch "little whitespaces". Quadrotrees can help you a little, but... I don't understand you solution
tell me more If you drop only 50 points, you'll not detect many little "white spaces" (when, for example, current radius 1e-3 less, than optimal. Obviously, such a solution will get WA.
How to check coverage with bruteforce? Intersect any two circles and consider epsilon neighborhood of their common points... Your idea is very good, but how you did it so fast? I have TL16 Apply some optimixation techniques - precalc, for instance... Apply some optimixation techniques - precalc, for instance... Now I have WA17 I do not understand what points should we check If we will check only neighboor points of intersection any 2 circles - it's not right For example 2 1000 1000 0 999 0 Right answer is 1999 But if we will check radius 1000 then both intersection points will lie out of main circle For each two crossing circles (crossing inside main circle) there must be third one which covers intersection point of the first two circles. can you tell me more about your solution how can you solve this problem without the diagram Where can I read about diagram of Voronoy? Preparata, Shajmos. Computational geometry. An introdution. |
