Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

MarioYC's blog

Is atan2 (C++) slow?
By MarioYC, 14 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

»
14 years ago, hide # |
 
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