Discussion @ 1332. Genie Bomber @ Timus Online Judge

Matov Dmitry How solve this problem with N <= 1000? [6] // Problem 1332. Genie Bomber 19 Jun 2006 11:43

Does anybody know an algorithm with lower than O(N^3) complexity?

exwRabbits_AlMag(VNTU) Just read HybridTheory's subject about it [2] // Problem 1332. Genie Bomber 19 Jun 2006 15:50

Matov Dmitry Re: Just read HybridTheory's subject about it [1] // Problem 1332. Genie Bomber 19 Jun 2006 18:05

I've already read this subject. And I can't imagine where did you find there the algorithm with lower than N^3 complexity.

exwRabbits_AlMag(VNTU) Sorry, my mistake. I really don't know. // Problem 1332. Genie Bomber 19 Jun 2006 18:36

BRAINIAC++ Re: How solve this problem with N <= 1000? // Problem 1332. Genie Bomber 19 Jun 2006 20:32

Burunduk1 Re: How solve this problem with N <= 1000? [1] // Problem 1332. Genie Bomber 20 Jun 2006 02:06

O(N^2logN)

Fix one point on the circle. This point becomes the begin of coordinates.
For each other point calculate interval of angles were center can be.
Now that you have intervals on the circle and you have to find
point which is covered by maximum number of intervals.

Matov Dmitry Re: How solve this problem with N <= 1000? // Problem 1332. Genie Bomber 20 Jun 2006 13:42

Thank you a lot. I got AC.

Discussion of Problem 1332. Genie Bomber