Обсуждение @ 1520. Империя наносит ответный удар @ Timus Online Judge

Hao Hu (Ikki @ Nanjing University) Can you give me a hint on how to solve this? [30] // Задача 1520. Империя наносит ответный удар 29 дек 2006 12:17

as the title
thanks in advance!

EFREMOV[USU] Re: Can you give me a hint on how to solve this? [28] // Задача 1520. Империя наносит ответный удар 29 дек 2006 15:02

Diagram of Voronoy, of course.

SPIRiT Re: Can you give me a hint on how to solve this? // Задача 1520. Империя наносит ответный удар 29 дек 2006 18:40

Well well, the second problem on Timus that should be solved with diagram of Voronoy

SPIRiT Re: Can you give me a hint on how to solve this? [24] // Задача 1520. Империя наносит ответный удар 29 дек 2006 18:40

Well well, the second problem on Timus that should be solved with diagram of Voronoy

Ignorance Re: Can you give me a hint on how to solve this? [23] // Задача 1520. Империя наносит ответный удар 29 дек 2006 19:05

What one was first?

Sawe Re: Can you give me a hint on how to solve this? [22] // Задача 1520. Империя наносит ответный удар 29 дек 2006 19:12

1504

Kit Re: Can you give me a hint on how to solve this? [21] // Задача 1520. Империя наносит ответный удар 30 дек 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.

EFREMOV[USU] Re: Can you give me a hint on how to solve this? [5] // Задача 1520. Империя наносит ответный удар 30 дек 2006 15:34

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.

Dmitry 'Diman_YES' Kovalioff. Retired Timus-1504 does not require voronoi graph either ;) (-) [4] // Задача 1520. Империя наносит ответный удар 30 дек 2006 19:25

SPIRiT Re: Timus-1504 does not require voronoi graph either ;) (-) [3] // Задача 1520. Империя наносит ответный удар 4 янв 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.

SPIRiT Are Saddams coordinates also integer or not [2] // Задача 1520. Империя наносит ответный удар 4 янв 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

Peter Ivanov Re: Are Saddams coordinates also integer or not // Задача 1520. Империя наносит ответный удар 5 янв 2007 20:01

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

Dmitry 'Diman_YES' Kovalioff. Retired Saddam's coordinates are not necessarily integer (+) // Задача 1520. Империя наносит ответный удар 5 янв 2007 20:57

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 ;)

323232 I need an AC solution to this problem [13] // Задача 1520. Империя наносит ответный удар 11 янв 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

Dmitry 'Diman_YES' Kovalioff. Retired Check your mail. I have sent you an exe-file of my solution (-) // Задача 1520. Империя наносит ответный удар 11 янв 2007 16:07

SPIRiT Probability will rule? [11] // Задача 1520. Империя наносит ответный удар 11 янв 2007 18:16

I think it's binary search + Monte-Carlo. Is such approach correct?

Edited by author 11.01.2007 18:16

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: Probability will rule? [10] // Задача 1520. Империя наносит ответный удар 16 янв 2007 15:15

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.

SPIRiT Re: Probability will rule? [8] // Задача 1520. Империя наносит ответный удар 17 янв 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?

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: Probability will rule? [7] // Задача 1520. Империя наносит ответный удар 18 янв 2007 16:46

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...

SPIRiT Re: Probability will rule? [2] // Задача 1520. Империя наносит ответный удар 18 янв 2007 17:21

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 :)

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: Probability will rule? // Задача 1520. Империя наносит ответный удар 19 янв 2007 14:30

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...

nttjuvwamsncc Re: Probability will rule? // Задача 1520. Империя наносит ответный удар 14 фев 2007 14:35

I don't understand you solution
tell me more

KirillB(Arkhangelsk - PomorSU) Re: Probability will rule? [3] // Задача 1520. Империя наносит ответный удар 19 янв 2007 14:46

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) писал(a) 18 января 2007 16:46

Your idea is very good, but how you did it so fast?
I have TL16

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) Re: Probability will rule? [2] // Задача 1520. Империя наносит ответный удар 22 янв 2007 14:55

Apply some optimixation techniques - precalc, for instance...

KirillB(Arkhangelsk - PomorSU) Re: Probability will rule? [1] // Задача 1520. Империя наносит ответный удар 22 янв 2007 19:13

Vedernikoff 'Goryinyich' Sergey (HSE: АОП) писал(a) 22 января 2007 14:55

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

it4.kp Re: Probability will rule? // Задача 1520. Империя наносит ответный удар 22 янв 2007 22:25

For each two crossing circles (crossing inside main circle) there must be third one which covers intersection point of the first two circles.

nttjuvwamsncc Re: Probability will rule? // Задача 1520. Империя наносит ответный удар 14 фев 2007 14:33

can you tell me more about your solution

nttjuvwamsncc Re: Can you give me a hint on how to solve this? // Задача 1520. Империя наносит ответный удар 14 фев 2007 14:33

how can you solve this problem without the diagram

Sawe Re: Can you give me a hint on how to solve this? [1] // Задача 1520. Империя наносит ответный удар 29 дек 2006 19:13

Where can I read about diagram of Voronoy?

EFREMOV[USU] Re: Can you give me a hint on how to solve this? // Задача 1520. Империя наносит ответный удар 29 дек 2006 23:05

Preparata, Shajmos. Computational geometry. An introdution.

Yogesh Re: Can you give me a hint on how to solve this? // Задача 1520. Империя наносит ответный удар 20 янв 2007 22:02

theriyaathutaa koothi

Обсуждение задачи 1520. Империя наносит ответный удар