arg_cmp/
lib.rs

1use ::std::cmp::Ordering;
2
3/// 2次元座標の偏角順
4///
5/// # Examples
6///
7/// ```
8/// use arg_cmp::ArgCmp;
9///
10/// let north = (0, 1);
11/// let south = (0, -1);
12/// let east = (1, 0);
13/// let west = (-1, 0);
14/// let mut points = vec![north, south, east, west];
15///
16/// points.sort_by_key(|&(x, y)| ArgCmp::new(x, y));
17///
18/// // 0°, 90°, 180°, 270°
19/// assert_eq!(points, vec![(1, 0), (0, 1), (-1, 0), (0, -1)]);
20/// ```
21///
22/// ## 偏角が等しい例
23///
24/// ```
25/// use arg_cmp::ArgCmp;
26///
27/// assert!(ArgCmp::new(1, 0).cmp(&ArgCmp::new(1, 0)).is_eq());
28/// assert!(ArgCmp::new(1, 0).cmp(&ArgCmp::new(2, 0)).is_eq());
29/// ```
30#[derive(Debug, PartialEq, Eq, Clone, Copy)]
31pub struct ArgCmp((i64, i64));
32
33/// 象限
34#[derive(Debug, PartialEq, Eq, PartialOrd, Ord, Clone, Copy)]
35pub enum Quadrant {
36    /// 1. [0°, 90°)
37    First,
38    /// 2. [90°, 180°)
39    Second,
40    /// 3. [180°, 270°)
41    Third,
42    /// 4. [270°, 360°)
43    Fourth,
44}
45
46impl ArgCmp {
47    /// # Panics
48    ///
49    /// if (x, y) is origin
50    pub fn new(x: i64, y: i64) -> Self {
51        assert_ne!((x, y), (0, 0));
52        Self((x, y))
53    }
54
55    pub fn x(&self) -> i64 {
56        self.0.0
57    }
58
59    pub fn y(&self) -> i64 {
60        self.0.1
61    }
62
63    fn is_lower_half(&self) -> bool {
64        self.y() < 0 || (self.y() == 0 && self.x() < 0)
65    }
66
67    /// 象限を返す
68    ///
69    /// # Examples
70    ///
71    /// ```
72    /// use arg_cmp::{ArgCmp, Quadrant};
73    ///
74    /// let north_east = ArgCmp::new(1, 1);
75    /// let north_west = ArgCmp::new(-1, 1);
76    /// let south_west = ArgCmp::new(-1, -1);
77    /// let south_east = ArgCmp::new(1, -1);
78    ///
79    /// assert_eq!(north_east.quadrant(), Quadrant::First);
80    /// assert_eq!(north_west.quadrant(), Quadrant::Second);
81    /// assert_eq!(south_west.quadrant(), Quadrant::Third);
82    /// assert_eq!(south_east.quadrant(), Quadrant::Fourth);
83    /// ```
84    pub fn quadrant(&self) -> Quadrant {
85        match (self.is_lower_half(), self.x().cmp(&0)) {
86            (false, Ordering::Greater) => Quadrant::First,
87            (false, _) => Quadrant::Second,
88            (true, Ordering::Less) => Quadrant::Third,
89            (true, _) => Quadrant::Fourth,
90        }
91    }
92}
93
94impl Ord for ArgCmp {
95    // https://atcoder.jp/contests/abc442/editorial/15136
96    fn cmp(&self, other: &Self) -> Ordering {
97        self.is_lower_half()
98            .cmp(&other.is_lower_half())
99            .then_with(||
100            // cross_product = self.x() * other.y() - self.y() * other.x() > 0
101            (self.y() * other.x()).cmp(&(self.x() * other.y())))
102    }
103}
104
105impl PartialOrd for ArgCmp {
106    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
107        Some(self.cmp(other))
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use crate::{ArgCmp, Quadrant};
114
115    #[test]
116    fn test_arg_cmp() {
117        // 0°, 45°, 90°, ...
118        let points = vec![
119            (1, 0),
120            (1, 1),
121            (0, 1),
122            (-1, 1),
123            (-1, 0),
124            (-1, -1),
125            (0, -1),
126            (1, -1),
127        ];
128
129        for i in 0..8 {
130            for j in 0..8 {
131                let (xi, yi) = points[i];
132                let (xj, yj) = points[j];
133                assert_eq!(ArgCmp::new(xi, yi).cmp(&ArgCmp::new(xj, yj)), i.cmp(&j));
134            }
135        }
136    }
137
138    #[test]
139    fn test_quadrant() {
140        // 0°, 45°, 90°, 135°, 180°, 225°, 270°, 315°
141        let points = vec![
142            (1, 0),
143            (1, 1),
144            (0, 1),
145            (-1, 1),
146            (-1, 0),
147            (-1, -1),
148            (0, -1),
149            (1, -1),
150        ];
151        let expected = vec![
152            Quadrant::First,
153            Quadrant::First,
154            Quadrant::Second,
155            Quadrant::Second,
156            Quadrant::Third,
157            Quadrant::Third,
158            Quadrant::Fourth,
159            Quadrant::Fourth,
160        ];
161        for (&(x, y), &q) in points.iter().zip(&expected) {
162            assert_eq!(ArgCmp::new(x, y).quadrant(), q);
163        }
164    }
165}
arg_cmp/lib.rs

arg_cmp/
lib.rs
