[Tutor] Sorting points on a 2D plane

[Robert Berman]

Hi,

I am working on a practice problem called 'POINTS' on the CodeChef
site:http://www.codechef.com/problems/POINTS/. This simply wants the sum
of the distances between a number of points on a 2 dimensional plane.
Looking at the problem, the algorithm to define the sum of the distances
between all the points is not really difficult.The challenge is in
ordering the points given the following rules:
1)  You cannot move to a point with a lesser X value as compared to
the  X value of the point you are on.
2)  For points having the same X value you need to visit the point with
the greatest Y value before visiting the new point with the same X
value. The least X takes precedence over the greatest Y.

In any given test case there can be from 2 to 100000 points. The X and Y
coordinates of each point will be between 0 and 10000 both inclusive.

OK. The rules are established. A properly constructed algorithm will
work for 10 points as well as 10000 points given it is properly
constructed. My point of confusion is in ordering the points. Given a
very simple example set of points:

0 5
0 1
0 2
2 1
2 3
5 2
5 1


The arrangement should be,

0 5
0 2
0 1
2 3
2 1
5 2
5 1

My solution is to first sort all the X values which would give me
0,0,0,2,2,5,5. I then will look at the Y values associated with the X
value so I know that I am going to sort 3 Y values in reverse order for
X = 0 and then append the Y value to each X point. 

What I am looking for is a better, faster approach. I think there would
be a way to build a dictionary but you can't use the X values as keys
since keys must be unique.

So, any help to point me in a better faster direction will be truly
appreciated.

Thanks,

Robert