competitive/geometry/
polygon.rs

1use super::{Approx, Ccw, Ccwable, Complex, TotalOrd};
2
3pub fn convex_hull<T>(mut ps: Vec<Complex<T>>) -> Vec<Complex<T>>
4where
5    T: PartialOrd + Ccwable,
6{
7    ps.sort_by(|p1, p2| ((p1.re, p1.im).partial_cmp(&(p2.re, p2.im)).unwrap()));
8    let mut qs = Vec::new();
9    for &p in ps.iter().chain(ps.iter().rev().skip(1)) {
10        while {
11            let k = qs.len();
12            k > 1 && matches!(Ccw::ccw(qs[k - 2], qs[k - 1], p), Ccw::Clockwise)
13        } {
14            qs.pop();
15        }
16        qs.push(p);
17    }
18    qs.pop();
19    qs
20}
21
22/// Return norm
23pub fn convex_diameter<T>(ps: &[Complex<T>]) -> T
24where
25    T: PartialOrd + Ccwable,
26{
27    let n = ps.len();
28    let mut i = (0..n).max_by_key(|&i| TotalOrd(ps[i].re)).unwrap_or(0);
29    let mut j = (0..n).min_by_key(|&i| TotalOrd(ps[i].re)).unwrap_or(0);
30    let mut res = (ps[i] - ps[j]).norm();
31    let (maxi, maxj) = (i, j);
32    loop {
33        let (ni, nj) = ((i + 1) % n, (j + 1) % n);
34        if Approx((ps[ni] - ps[i]).cross(ps[nj] - ps[j])) < Approx(T::zero()) {
35            i = ni;
36        } else {
37            j = nj;
38        }
39        let d = (ps[i] - ps[j]).norm();
40        if res < d {
41            res = d;
42        }
43        if i == maxi && j == maxj {
44            break;
45        }
46    }
47    res
48}
competitive/geometry/polygon.rs

competitive/geometry/
polygon.rs
