Discussion @ 1332. Genie Bomber @ Timus Online Judge

How solve this problem with N <= 1000?

Posted by Matov Dmitry 19 Jun 2006 11:43

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

Just read HybridTheory's subject about it

Posted by Alexey 19 Jun 2006 15:50

Re: Just read HybridTheory's subject about it

Posted by Matov Dmitry 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.

Sorry, my mistake. I really don't know.

Posted by Alexey 19 Jun 2006 18:36

Re: How solve this problem with N <= 1000?

Posted by Aybek Bukabayev 19 Jun 2006 20:32

Re: How solve this problem with N <= 1000?

Posted by Burunduk1 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.

Re: How solve this problem with N <= 1000?

Posted by Matov Dmitry 20 Jun 2006 13:42

Thank you a lot. I got AC.

Discussion of Problem 1332. Genie Bomber