1 Тема от MSDN

  • MSDN
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-09
  • Сообщений: 40

Тема: timus 1429

http://acm.timus.ru/problem.aspx?space=1&num=1429

Здравствуйте! Собственно задачу я сдал, но вот смутил тот факт у меня решение прошло за 1.7 секунды, а у большей части авторов время около 0,3, ну вообщем меньше секунды.
Идея простая воспользоваться формулой эйлера. Тоесть по сути надо посчитать в графе число вершин, ребер и компонент связности. Берем окружность и смотрим пересечения со всеми остальными и каждое пересечение (точки) запихиваем в сет. Ну и в конце сей операции мы получим число всех различных точек на этой окружности и собственно очевидно что к ребер между ними столько же. Получается асмиптотика O(N^2*log(N))

Кто нибудь подскажите решение с лучшей асмиптотикой...

2 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: timus 1429

Интересно как они в 300 KB укладываются - как-то же надо определить новая эта точка пересечения или нет.
У меня тоже получилось только за 1.3 сдать с похожим алгоритмом.

3 Ответ от Oleg

  • Oleg
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-09-22
  • Сообщений: 86

Re: timus 1429

Сам себе подсказал. smile

Что б добиться такого времени - храни в sete только точки для текущего круга, а не все вместе. а totalPoints изменяй вручную:

if (i < j && edges.find(p) == edges.end())
   totalPoints++;

Получается экономия и по памяти и по времени.