| ENG RUS | Timus Online Judge |
Discussion of Problem 1369. Cockroach RaceSafe Bird I wonder whether this problem is solved by VORONOI graph? [12] // Problem 1369. Cockroach Race 4 May 2005 15:13 I wonder whether this problem is solved by VORONOI graph? Виктор Крупко Re: I wonder whether this problem is solved by VORONOI graph? [11] // Problem 1369. Cockroach Race 4 May 2005 22:22 You could not explain or send me of the theory about VORONOI graph xxvictorxx@mail.ru, please. (In Russian) N.M.Hieu ( DHSP ) Re: I wonder whether this problem is solved by VORONOI graph? [10] // Problem 1369. Cockroach Race 9 Jun 2005 17:10 Safe Bird , Can you please tell me ( or send an email to me ) the theory about VORONOI graph ? I haven't known it yet ! Thank you very much ! Виктор Крупко Re: I wonder whether this problem is solved by VORONOI graph? [9] // Problem 1369. Cockroach Race 10 Jun 2005 00:30 Already 2 persons ask can will share experience. Please!!! Avanesov Re: I wonder whether this problem is solved by VORONOI graph? // Problem 1369. Cockroach Race 22 Jun 2005 17:59 In english search google for "voronoi diagram" One of the links in english: http://algolist.manual.ru/maths/geom/voronoi/index.php in Russian - search google for Диаграмма Вороного There are a lot of articles Edited by author 22.06.2005 18:04 Safe Bird Just came here. Is it really solved by VORONOI? [7] // Problem 1369. Cockroach Race 5 Jul 2005 16:14 "You could not explain or send me of the theory about VORONOI graph" "Already 2 persons ask can will share experience. Please!!!" this is not my obligation to answer your question!! i may and may not answer it. you can't command me at least. I'd like to answer N.M.Hieu because more or less he show some respect and is really "asking for" my reply. (but the response has been written out so i don't need to send him the e-mail) Edited by author 05.07.2005 16:15 N.M.Hieu ( DHSP ) Re: Just came here. Is it really solved by VORONOI? [6] // Problem 1369. Cockroach Race 8 Jul 2005 23:27 To Safe Bird, I'm sorry to bother you again ! I have read Fortune's method but I haven't understood what is "parabolic front" and the intersections between the coin and the plane pi ( pi = 3.14...). I think it always the surface of the coin because the coin and the plane are slanted for an angle = 45. ( Maybe I have misunderstood ) If you are not busy ! Please explain Fortune's method more clearly for me ! My e_mail address : hard7771988@yahoo.co.uk ! Thank you ! Cold Weather Re: Just came here. Is it really solved by VORONOI? [3] // Problem 1369. Cockroach Race 9 Jul 2005 10:20 To everyone who has accepted ! Would you please tell me the way to store the memory ? I think my solution is right but it need many memories ! So I can't pass test#24 ! I have an array B : array[1..10000,1..700] to store the answer and after that I Sort them by QuickSort but with one point in set M , maybe it > 700 so I died ! Please help me ! Safe Bird How do you solve the problem? (if the memory is not taken into account) [2] // Problem 1369. Cockroach Race 15 Jul 2005 17:37 Cold Weather Re: How do you solve the problem? (if the memory is not taken into account) [1] // Problem 1369. Cockroach Race 16 Jul 2005 10:00 I create Voronoi diagram for N cockroaches with Complexity : O (NlogN) ! After that I calculate with all the Sweet cakes ! with one sweet cake I use an algorithm with complexity = O(logn) to get all the cockroaches nearest this sweet cake ! I think may be I'm wrong because I store all the cockroaches of all the cakes ! Maybe I can do with each cake ! Hope that I have enough time to AC. Thank you Dmitry ! I think it's a good structure ! Orenburg SU 7 What is the 30 test case? // Problem 1369. Cockroach Race 1 Jan 2006 22:25 What is the 30 test case? I write several solution and all have TLE on 30 test case. Safe Bird In fact i HAVEN'T solved this problem! [1] // Problem 1369. Cockroach Race 15 Jul 2005 17:35 I'm also wondering the ways to solve it~!!! sigh Dmitry 'Diman_YES' Kovalioff Quad-tree. I haven't written my solution yet, but the original jury solution used it (-) // Problem 1369. Cockroach Race 15 Jul 2005 22:42 |