How to sort points in clockwise/counter-clockwise order efficiently? I use atan2 to get angle created by Ox axis and point but it seems slow and sometimes it causes precision error. Appreciate for any help.
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | Dominater069 | 154 |
8 | awoo | 154 |
10 | luogu_official | 150 |
How to sort points in clockwise/counter-clockwise order efficiently? I use atan2 to get angle created by Ox axis and point but it seems slow and sometimes it causes precision error. Appreciate for any help.
Name |
---|
Check and compare the quadrants first, then do a CCW calculation only if two points are in the same quadrant.
You can use cross product. For example this is the solution for URI 2541.
The indexes of points are sorted here.