competitive_programming_rs/geometry/
convex_hull.rs

1pub fn extract_convex_hull(points: &[Point], contain_on_segment: bool) -> Vec<usize> {
2    let n = points.len();
3    if n <= 1 {
4        return vec![0];
5    }
6
7    let mut ps: Vec<usize> = (0..n).collect();
8    ps.sort_by(|&a, &b| {
9        if (points[a].x - points[b].x).abs() < std::f64::EPSILON {
10            points[a].y.partial_cmp(&points[b].y).unwrap()
11        } else {
12            points[a].x.partial_cmp(&points[b].x).unwrap()
13        }
14    });
15
16    let mut qs: Vec<usize> = Vec::new();
17    for &i in &ps {
18        while qs.len() > 1 {
19            let k = qs.len();
20            let det = (points[qs[k - 1]] - points[qs[k - 2]]).det(&(points[i] - points[qs[k - 1]]));
21            if det < 0.0 || (det <= 0.0 && !contain_on_segment) {
22                qs.pop();
23            } else {
24                break;
25            }
26        }
27        qs.push(i);
28    }
29
30    let t = qs.len();
31    for i in (0..(n - 1)).rev() {
32        let i = ps[i];
33        while qs.len() > t {
34            let k = qs.len();
35            let det = (points[qs[k - 1]] - points[qs[k - 2]]).det(&(points[i] - points[qs[k - 1]]));
36            if det < 0.0 || (det <= 0.0 && !contain_on_segment) {
37                qs.pop();
38            } else {
39                break;
40            }
41        }
42        qs.push(i);
43    }
44
45    qs.pop();
46    qs
47}
48
49#[derive(Debug, Copy, Clone)]
50pub struct Point {
51    x: f64,
52    y: f64,
53}
54
55impl std::ops::Sub for Point {
56    type Output = Point;
57    fn sub(self, other: Point) -> Point {
58        Point {
59            x: self.x - other.x,
60            y: self.y - other.y,
61        }
62    }
63}
64
65impl Point {
66    pub fn det(&self, other: &Point) -> f64 {
67        self.x * other.y - self.y * other.x
68    }
69}
70
71#[cfg(test)]
72mod test {
73    use super::*;
74    use crate::utils::test_helper::Tester;
75
76    /// Solve http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A
77    #[test]
78    fn solve_cgl_4_a() {
79        let tester = Tester::new("./assets/CGL_4_A/in/", "./assets/CGL_4_A/out/");
80        tester.test_solution(|sc| {
81            let n: usize = sc.read();
82            let mut points = Vec::new();
83            for _ in 0..n {
84                let x: f64 = sc.read();
85                let y: f64 = sc.read();
86                points.push(Point { x, y });
87            }
88
89            let convex_hull = extract_convex_hull(&points, true);
90            sc.write(format!("{}\n", convex_hull.len()));
91
92            let n = convex_hull.len();
93            let mut start = 0;
94            for i in 0..n {
95                if points[convex_hull[i]].y < points[convex_hull[start]].y
96                    || (points[convex_hull[i]].y == points[convex_hull[start]].y
97                        && points[convex_hull[i]].x < points[convex_hull[start]].x)
98                {
99                    start = i;
100                }
101            }
102
103            for i in 0..n {
104                let i = (i + start) % n;
105                let i = convex_hull[i];
106                sc.write(format!("{} {}\n", points[i].x, points[i].y));
107            }
108        });
109    }
110}
competitive_programming_rs/geometry/convex_hull.rs

competitive_programming_rs/geometry/
convex_hull.rs
