MarioYC's blog

Is atan2 (C++) slow?
By MarioYC, 13 years ago, In English

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

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
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).

→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thanks, now it works in about 2-2.5s, getting WA though.
    → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Could it be a problem because two points get a similar value for atan2?
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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).
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Now I've changed it and use only the ccw function, but still getting WA :(

        Code: http://pastie.org/3110758
        → Reply