Can you give me a hint on how to solve this?
as the title
thanks in advance!
Re: Can you give me a hint on how to solve this?
Diagram of Voronoy, of course.
Re: Can you give me a hint on how to solve this?
Posted by
SPIRiT 29 Dec 2006 18:40
Well well, the second problem on Timus that should be solved with diagram of Voronoy
Re: Can you give me a hint on how to solve this?
Posted by
SPIRiT 29 Dec 2006 18:40
Well well, the second problem on Timus that should be solved with diagram of Voronoy
Re: Can you give me a hint on how to solve this?
What one was first?
Re: Can you give me a hint on how to solve this?
Posted by
Sawe 29 Dec 2006 19:12
1504
Re: Can you give me a hint on how to solve this?
Posted by
Sawe 29 Dec 2006 19:13
Where can I read about diagram of Voronoy?
Re: Can you give me a hint on how to solve this?
Preparata, Shajmos. Computational geometry. An introdution.
Re: Can you give me a hint on how to solve this?
Posted by
Kit 30 Dec 2006 12:42
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.
Re: Can you give me a hint on how to solve this?
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.
Timus-1504 does not require voronoi graph either ;) (-)
Re: Timus-1504 does not require voronoi graph either ;) (-)
Posted by
SPIRiT 4 Jan 2007 17:01
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.
Are Saddams coordinates also integer or not
Posted by
SPIRiT 4 Jan 2007 18:57
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
Re: Are Saddams coordinates also integer or not
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
Saddam's coordinates are not necessarily integer (+)
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 ;)
I need an AC solution to this problem
Posted by
323232 11 Jan 2007 15:58
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
Check your mail. I have sent you an exe-file of my solution (-)
Probability will rule?
Posted by
SPIRiT 11 Jan 2007 18:16
I think it's binary search + Monte-Carlo. Is such approach correct?
Edited by author 11.01.2007 18:16
Re: Probability will rule?
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.
Re: Probability will rule?
Posted by
SPIRiT 17 Jan 2007 19:01
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?
