Обсуждение @ 1332. Джинн-бомбардировки @ Timus Online Judge

Matov Dmitry How solve this problem with N <= 1000? [6] // Задача 1332. Джинн-бомбардировки 19 июн 2006 11:43

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

Alexey Just read HybridTheory's subject about it [2] // Задача 1332. Джинн-бомбардировки 19 июн 2006 15:50

Matov Dmitry Re: Just read HybridTheory's subject about it [1] // Задача 1332. Джинн-бомбардировки 19 июн 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.

Alexey Sorry, my mistake. I really don't know. // Задача 1332. Джинн-бомбардировки 19 июн 2006 18:36

Aybek Bukabayev Re: How solve this problem with N <= 1000? // Задача 1332. Джинн-бомбардировки 19 июн 2006 20:32

Burunduk1 Re: How solve this problem with N <= 1000? [1] // Задача 1332. Джинн-бомбардировки 20 июн 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? // Задача 1332. Джинн-бомбардировки 20 июн 2006 13:42

Thank you a lot. I got AC.

Обсуждение задачи 1332. Джинн-бомбардировки