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. I do it like this (tested on 68208420).
sort(v.begin(), v.end(), [] (point a, point b) {
bool x = a.y >= 0, y = b.y >= 0;
return x == y ? a.x * b.y > a.y * b.x : x < y;
});
Just wondering if there's something even shorter.
Update: the above code works only for set of points with no three collinear. The following version (way longer) seems to work for all inputs.
inline int quad (point p) {
if (p.x < 0 and p.y < 0) return 0;
if (p.x >= 0 and p.y < 0) return 1;
if (p.x >= 0 and p.y >= 0) return 2;
if (p.x < 0 and p.y >= 0) return 3;
assert(69 == 420);
}
sort(v.begin(), v.end(), [] (point a, point b) {
return quad(a) == quad(b) ? a.x * b.y > a.y * b.x : quad(a) < quad(b);
});