Angular Sorting
hello , my friends
This is my first blog and I want to share some knowledge that may help other to solve some problems and
if you have another algorithm you can explain it in comments .
Let's start , you are given n points . each point is at integer coordinates (x,y) . can you sort them in clockwise order and vice versa ?
the points are here like that
Think about it for a bit and then continue with me ...
if we have slope from each point and (0,0) ?
Nice , we can get angle with x-axis and from this we can sort them !!
we can see like this
let's calculate the angle
angle = atan2(y,x) — in redius .
angle = atan2(y,x) * 180 /PI — this is in degree .
but what about negative angles ?!
we can add 360 degree to be positive .
angle+=(angle<0)*360 .
code in C++ https://ideone.com/fork/MXtcfD
Problem related to this concept https://codeforces.me/gym/103562/problem/D
In the end, I hope this blog is useful and that you like it . I will be happy with your comment :)
Thank you
C'mon man. You are a lgm. What a question?!
Using complex and using arg function worked for me in a problem.
using atan2 to sort is pretty cringe (and inaccurate), use the CCW function instead
why?! , I got accepted in some problem with absolute error doesn't exceed 1e-6
I know the CCW but I don't know that tan2(y,x) is inaccurate .
Mostly two reasons: 1. It's slow, as all floating point math are. 2. It's inaccurate, as all floating point math are.
Thank you
What is CCW?
short for Counter-ClockWise: basically using the sign of the dot product to check if three dots (or two vectors) are placed clockwise or counter-clockwise.
ايوة يابيبو ياحلاااق
ATTENTION!
If the pint (0,0) is not in center of the points, it may give an error. see the following test case: 4 4 0 2 1 3 3 4 3
To solve this error, you may calculate the angles using the center point of all these points instead of (0,0). center point can be calculated using ((x1+x2+x3+...+xn)/n, (y1+y2+y3+...+yn)/n)