ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1369. Cockroach Race

I wonder whether this problem is solved by VORONOI graph?
Posted by Safe Bird 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?
Posted by Виктор Крупко 4 May 2005 22:22
You could not explain or send me of the theory about VORONOI graph
xxvictorxx@mail.ru, please. (In Russian)
Re: I wonder whether this problem is solved by VORONOI graph?
Posted by N.M.Hieu ( DHSP ) 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?
Posted by Виктор Крупко 10 Jun 2005 00:30
Already 2 persons ask can will share experience.
Please!!!
Re: I wonder whether this problem is solved by VORONOI graph?
Posted by Avanesov 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
Just came here. Is it really solved by VORONOI?
Posted by Safe Bird 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
Re: Just came here. Is it really solved by VORONOI?
Posted by N.M.Hieu ( DHSP ) 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 !
Re: Just came here. Is it really solved by VORONOI?
Posted by Cold Weather 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 !
In fact i HAVEN'T solved this problem!
Posted by Safe Bird 15 Jul 2005 17:35
I'm also wondering the ways to solve it~!!! sigh
How do you solve the problem? (if the memory is not taken into account)
Posted by Safe Bird 15 Jul 2005 17:37
Quad-tree. I haven't written my solution yet, but the original jury solution used it (-)
Posted by Dmitry 'Diman_YES' Kovalioff 15 Jul 2005 22:42
Re: How do you solve the problem? (if the memory is not taken into account)
Posted by Cold Weather 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 !
What is the 30 test case?
Posted by Orenburg SU 7 1 Jan 2006 22:25
What is the 30 test case?
I write several solution and all have TLE on 30 test case.