TIMUS - 1207 Median on the plane

Link to the problem on Timus Online Judge

 This is a Computational Geometry problem. No 3 points lie on the same line and this is a great help about our approach to the problem. Since no three points lie on the same line, if you choose point A there is another point B which line AB divides all points equally. I choose the first point according to dictionary order, then if you can sort other points in increasing order of angle relating to the first point, then the other point would be obvious.

 

As you see in the figure I've chosen point 0 and want to sort other points in the given order(so the answer would be point 4 in this case), Surprisingly the problem reduces to a sorting problem and we know we can sort in O(n log n). We need to write a comparator for two points, I mean we need to identify between two points x and y which one comes earlier in the sorted list?

And how do we write the comparator? If the cross product of vector x-v[0] and x-y is negative then x-v[0]-y are clockwise, otherwise they are counter-clockwise.

At last we use function comp to sort other points.
sort(v.begin()+1, v.end(), comp);