Say yo want a set of points sorted in some counterclockwise order. What is the best (fast, precise, short) way to do it? The `atan2l`

function is precise and short but way too slow.

**Update**: One of the previous entries were wrong. I like the following one which hopefully works.

```
inline bool up (point p) {
return p.y > 0 or (p.y == 0 and p.x >= 0);
}
sort(v.begin(), v.end(), [] (point a, point b) {
return up(a) == up(b) ? a.x * b.y > a.y * b.x : up(a) < up(b);
});
```

if you look at each point as a complex number, then imagine you wana sort points by counterclockwise order from P, your sort can be like this:

if you wana know how does it work search about complex in Codeforces might be helpful. I know 2 of them first_one introduce some functions about complex and second_one is about FFT but has useful parts about complex too.

This compare function won't change order of the points on X-axis (y=0). Try this: (-1, 0), (1, 0),(-2,0), (2,0), (0,3).

It's ok I think I got acc with this CMP in today's contest ;)

(1, 0) == (-1, 0) according to your comparator. But I'm actually interested if there's an elegant way to do this as well.

arg((1, 0)) = 0

arg((-1, 0)) = 3.1415(PI)

and these are in radians.

Good points (no pun intended), thanks shourov.sust and mmaxio. I guess this one works only when no three points are collinear. Nevertheless, I used a different version before.

This one seems to be correct for all inputs (although a bit longer). So the question remains.

If you want

shorter:I mean, if we're going to golf it ..

EDIT: What about this cursed version relying on operator precedence rules?

Auto comment: topic has been updated by Alpha_Q (previous revision, new revision, compare).I like to use something very similar to your code. First I divide the plane into two half-open $$$180^\circ$$$ angles (by comparing

lexicographicallywith origin), then use the cross product directly. All the relative angles will be smaller than $$$180^\circ$$$, so it'll work.Looks quite long (but nice), but we can make it shorter and messier, too:

You can also use

`atan2`

without worrying about precision issues with a simple hack. If the angles differ by more than, say, $$$0.1$$$, you compare the angles directly, otherwise you directly use the cross product.BTW why try to make the code as short as possible? If you're not code golfing, you should rather aim for readability. It pays off when debugging (at least it works for me).

Thanks for sharing. You're right about readability. I guess I just wanted to look at some elegant ways to do it from different people.

Also since I use

`std::pair`

directly as my point structure, this is less messy for me.(EDIT: I think I was mistaken in the first part, sorry.)

What I do is very similar to what mnbvmar described. I use function

and then sort points as you did replacing your quad function with my IsInUpper function.

This is exactly what I was looking for, thank you.

I actually tried the first snippet for the first time today, and getting AC misled me to believe it's correct for all inputs. It seems like I only needed to differentiate between the two sides of x-axis to get it right.

I'll update the blog with the following snippet only.

this code is adapted from the one given here

It's already described in this old blog: Geometry: 2D points and lines [Tutorial] — Codeforces. Partition by

`isInUpper`

(use`partition`

function) then sort each part with cross product.Code copied from the old blogWhen there's no point coincide with the origin, the first partition is not necessary.

I'd add that

`a.x * b.y > a.y * b.x`

works fine as long as all your points are in the same strict half plane whose border contains $$$(0,0)$$$.In the end, in Goodbye E, I ended up fixing one point P, splitting the other points into those on the left side of the line origin-P and those on the right side, and sorting those on each side by their cosine with respect to the ray origin->P. Basically, I removed the circularity that complicates polar sorting and the rest is just 2 pointers.