Is there an efficienct way to sort radially about a point in general positions without using double? (If all the inputs are integer?)
Can we ignore using arccos( dotproduct )?
Sorting by angle?
Moderator: Board moderators

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
I think that's possible, when coordinates of point, which is centre of sort are integers too. You may use fractions to sort (remember nominator and denominator as two numbers). Of course if I don't make any mistake in this thoughts ...
Best regards
DM
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
It is not dot product that you should use, but cross product. If you make a cross product of the two vectors coming out of the center point to the two points you are comparing, the sign of the product will do the job, and the value of the product is an integer if the coordinates are integers.Can we ignore using arccos( dotproduct )?
However, there is another point that confuses me. How can you sort elements that have a circular relation?? (i.e. there is no 'smallest' or 'largest' element. However, there is an wellknown order any rotations of which will do.)

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Nod, of course I know the cross product approach to determine if a point is left of another line, but it's not a true order in the sense that there's no absolute min.. since you can keep going around in a circle.. and really don't want to use an O(n^2) sort, because that kills the point..
ANy other hints/clues?
ANy other hints/clues?
There is a solution that I just thought about. Why do not you take an arbitrary point of them, and divide the points into two halves one above and one below the line connecting the point taken and the center point. Now you can order the two parts independently (and they will have no circular relation this time), then concatenate the two sorted parts into the final result.
I just invented this, and I do not know if it will work, but I think it should. Any special cases you can think of?
One other question: Are there other situations when we try to sort a set of objects where there is such a circular relation other than in sorting a set of points? Please tell me if you have any examples.
I just invented this, and I do not know if it will work, but I think it should. Any special cases you can think of?
One other question: Are there other situations when we try to sort a set of objects where there is such a circular relation other than in sorting a set of points? Please tell me if you have any examples.
Translate the entire coordinate system such that the rotation point is now 0,0. Then, you can label each point to be in Quadrants I, II, III, or IV depending on the sign of the x,y values. If the points are in the same quadrant, use some kind of fractional comparator, where the fractions are the dy/dx slopes of the two points with respect to the origin.
Assuming you use LCM to determine which numerator is bigger, this should have a running time of approximately n log n log n using quicksort. You can of course use integer division first to make sure you really need to use any fraction comparisons to drop the runtime further.
This, to the best of my knowledge, avoids any use of doubles.
I'm sure there's can be a more efficient way of doing it though.
Assuming you use LCM to determine which numerator is bigger, this should have a running time of approximately n log n log n using quicksort. You can of course use integer division first to make sure you really need to use any fraction comparisons to drop the runtime further.
This, to the best of my knowledge, avoids any use of doubles.
I'm sure there's can be a more efficient way of doing it though.