competitive_programming_rs/geometry/
mod.rs

1pub mod circle;
2pub mod convex_hull;
3pub mod minimum_bounding_circle;
4
5pub mod basic {
6    #[derive(Copy, Clone, Debug)]
7    pub struct Point<T> {
8        pub x: T,
9        pub y: T,
10    }
11
12    impl<T> Point<T>
13    where
14        T: std::ops::Mul<T, Output = T> + std::ops::Sub<T, Output = T> + Copy,
15    {
16        pub fn det(&self, p: Point<T>) -> T {
17            self.x * p.y - self.y * p.x
18        }
19    }
20
21    impl<T> std::ops::Add for Point<T>
22    where
23        T: std::ops::Add<T, Output = T>,
24    {
25        type Output = Self;
26
27        fn add(self, rhs: Self) -> Self::Output {
28            Point {
29                x: self.x + rhs.x,
30                y: self.y + rhs.y,
31            }
32        }
33    }
34
35    impl<T> std::ops::Sub for Point<T>
36    where
37        T: std::ops::Sub<T, Output = T>,
38    {
39        type Output = Self;
40
41        fn sub(self, rhs: Self) -> Self::Output {
42            Point {
43                x: self.x - rhs.x,
44                y: self.y - rhs.y,
45            }
46        }
47    }
48    impl<T> std::ops::Mul<T> for Point<T>
49    where
50        T: std::ops::Mul<T, Output = T> + Copy,
51    {
52        type Output = Self;
53
54        fn mul(self, rhs: T) -> Self::Output {
55            Point {
56                x: self.x * rhs,
57                y: self.y * rhs,
58            }
59        }
60    }
61
62    pub struct Segment<T> {
63        pub from: Point<T>,
64        pub to: Point<T>,
65    }
66
67    impl<T> Segment<T>
68    where
69        T: PartialOrd
70            + Copy
71            + PartialEq
72            + std::ops::Add<T, Output = T>
73            + std::ops::Sub<T, Output = T>
74            + std::ops::Mul<T, Output = T>
75            + std::ops::Div<T, Output = T>,
76    {
77        pub fn cross_point(&self, seg: &Segment<T>) -> Option<Point<T>> {
78            let (a, b) = (self.from, self.to);
79            let (c, d) = (seg.from, seg.to);
80            let dc = d - c;
81            let ba = b - a;
82            if dc.x * ba.y == dc.y * ba.x {
83                return None;
84            }
85
86            let p = a + (b - a) * ((a - c).det(d - c) / (d - c).det(b - a));
87            Some(p)
88        }
89    }
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95    use crate::utils::test_helper::Tester;
96
97    /// Solve http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_2_C
98    #[test]
99    fn solve_cgl_2_c() {
100        use basic::*;
101        let tester = Tester::new("./assets/CGL_2_C/in/", "./assets/CGL_2_C/out/");
102        tester.test_solution_with(
103            |sc| {
104                let q: usize = sc.read();
105                for _ in 0..q {
106                    let t: Vec<f64> = sc.vec(8);
107                    let seg1 = Segment {
108                        from: Point { x: t[0], y: t[1] },
109                        to: Point { x: t[2], y: t[3] },
110                    };
111                    let seg2 = Segment {
112                        from: Point { x: t[4], y: t[5] },
113                        to: Point { x: t[6], y: t[7] },
114                    };
115                    let p = seg1.cross_point(&seg2).unwrap();
116                    sc.write(format!("{} {}\n", p.x, p.y));
117                }
118            },
119            |expected, actual| {
120                assert!((expected.read::<f64>() - actual.read::<f64>()).abs() < 1e-6);
121                assert!((expected.read::<f64>() - actual.read::<f64>()).abs() < 1e-6);
122            },
123        );
124    }
125}
competitive_programming_rs/geometry/mod.rs

competitive_programming_rs/geometry/
mod.rs
