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

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

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
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится
Nope.. It's just you blink so fast...
→ Ответить
»
13 лет назад, # |
  Проголосовать: нравится +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).

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Thanks, now it works in about 2-2.5s, getting WA though.
    → Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Could it be a problem because two points get a similar value for atan2?
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      You can sort any points with integer coordinates without using atan2 (y=0 line splits the plain; use wedge product instead of atan2 in each part).
      → Ответить
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Now I've changed it and use only the ccw function, but still getting WA :(

        Code: http://pastie.org/3110758
        → Ответить
»
13 лет назад, # |
  Проголосовать: нравится 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.
→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Don't forget to switch comment's language.

    Atan2 doesn't call cos and sin. It calls atan, sqrt and division.
    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      I can't chage laguage on ipad. Maybe atan calls cos and sin? Anyway its complexity O(20-24)
      → Ответить