Обсуждение @ 1369. Тараканьи бега @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

I wonder whether this problem is solved by VORONOI graph? Safe Bird 4 май 2005 15:13

I wonder whether this problem is solved by VORONOI graph?

Re: I wonder whether this problem is solved by VORONOI graph? Виктор Крупко 4 май 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? N.M.Hieu ( DHSP ) 9 июн 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? Виктор Крупко 10 июн 2005 00:30

Already 2 persons ask can will share experience.
Please!!!

Re: I wonder whether this problem is solved by VORONOI graph? Avanesov 22 июн 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? Safe Bird 5 июл 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? N.M.Hieu ( DHSP ) 8 июл 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? Cold Weather 9 июл 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 !

How do you solve the problem? (if the memory is not taken into account) Safe Bird 15 июл 2005 17:37

Re: How do you solve the problem? (if the memory is not taken into account) Cold Weather 16 июл 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? Orenburg SU 7 1 янв 2006 22:25

What is the 30 test case?
I write several solution and all have TLE on 30 test case.

In fact i HAVEN'T solved this problem! Safe Bird 15 июл 2005 17:35

I'm also wondering the ways to solve it~!!! sigh

Quad-tree. I haven't written my solution yet, but the original jury solution used it (-) Dmitry 'Diman_YES' Kovalioff 15 июл 2005 22:42

Обсуждение задачи 1369. Тараканьи бега