Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

Блог пользователя MarioYC

Is atan2 (C++) slow?
Автор MarioYC, 14 лет назад, По-английски

Hi, I was trying to solve this problem : http://livearchive.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=2065

However I get TLE, the complexity of my algorithm is O(n^2 lg n) which I think is enough. So I was wondering if using atan2 to order points by polar angle is slow?

Code : http://pastie.org/3105825

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
14 лет назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится
Nope.. It's just you blink so fast...
→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится
You can extend your 'point' struct and precalculate angles for points before sorting them. Now you have calls of atan2, and after precalculation you'll have only O(n2).

→ Ответить
»
14 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
atan2 calls functions cos and sin. Each of them have complexity O(10-12), because to calc the result of function they use Taylor series.
→ Ответить