How solve this problem with N <= 1000?

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

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?

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

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?

Thank you a lot. I got AC.