haar_lib/geom_int/
arg_sort.rs

1//! 偏角ソート
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/sort_points_by_argument>
5use std::cmp::Ordering;
6
7use crate::geom_int::*;
8
9/// 偏角ソートした`Vec`を返す。
10///
11/// 偏角($-\pi \lt \arg \le \pi$)で点をソートする。
12/// ただし、点(0,0)は偏角が0とする。
13pub fn arg_sort(a: Vec<VectorInt>) -> Vec<VectorInt> {
14    let mut ret = vec![];
15
16    let mut upper = vec![];
17    let mut lower = vec![];
18    let mut zero = vec![];
19    let mut x_plus = vec![];
20    let mut x_minus = vec![];
21
22    for p in a {
23        match p.y.cmp(&0) {
24            Ordering::Equal => match p.x.cmp(&0) {
25                Ordering::Greater => x_plus.push(p),
26                Ordering::Less => x_minus.push(p),
27                Ordering::Equal => zero.push(p),
28            },
29            Ordering::Greater => upper.push(p),
30            Ordering::Less => lower.push(p),
31        }
32    }
33
34    upper.sort_by(|p, q| q.cross(*p).cmp(&0));
35    lower.sort_by(|p, q| q.cross(*p).cmp(&0));
36
37    ret.extend(lower);
38    ret.extend(x_plus);
39    ret.extend(zero);
40    ret.extend(upper);
41    ret.extend(x_minus);
42
43    ret
44}