competitive_programming_rs/geometry/
circle.rs

1pub fn cc_intersect((p1, r1): (Point, f64), (p2, r2): (Point, f64)) -> Vec<Point> {
2    let dist = (p1 - p2).abs();
3    if dist > r1 + r2 {
4        return Vec::new();
5    }
6
7    let rc = (dist * dist + r1 * r1 - r2 * r2) / (2. * dist);
8    let rs = (r1 * r1 - rc * rc).sqrt();
9    let diff = (p2 - p1) / dist;
10    vec![p1 + diff * Point(rc, rs), p1 + diff * Point(rc, -rs)]
11}
12
13#[derive(Copy, Clone)]
14pub struct Point(f64, f64);
15
16impl Point {
17    fn abs(self) -> f64 {
18        let x = self.0;
19        let y = self.1;
20        (x * x + y * y).sqrt()
21    }
22}
23
24impl ::std::ops::Add<Point> for Point {
25    type Output = Point;
26    fn add(self, rhs: Point) -> Point {
27        Point(self.0 + rhs.0, self.1 + rhs.1)
28    }
29}
30
31impl ::std::ops::Sub<Point> for Point {
32    type Output = Point;
33    fn sub(self, rhs: Point) -> Point {
34        Point(self.0 - rhs.0, self.1 - rhs.1)
35    }
36}
37
38impl ::std::ops::Div<f64> for Point {
39    type Output = Point;
40    fn div(self, rhs: f64) -> Point {
41        Point(self.0 / rhs, self.1 / rhs)
42    }
43}
44
45impl ::std::ops::Mul<Point> for Point {
46    type Output = Point;
47    fn mul(self, rhs: Point) -> Point {
48        let Point(x1, y1) = self;
49        let Point(x2, y2) = rhs;
50        Point(x1 * x2 - y1 * y2, x1 * y2 + y1 * x2)
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57    use crate::utils::test_helper::Tester;
58
59    #[test]
60    fn solve_cgl_7_e() {
61        let tester = Tester::new("./assets/CGL_7_E/in/", "./assets/CGL_7_E/out/");
62        tester.test_solution_with(
63            |sc| {
64                let c1 = (Point(sc.read(), sc.read()), sc.read());
65                let c2 = (Point(sc.read(), sc.read()), sc.read());
66
67                let mut points = cc_intersect(c1, c2)
68                    .into_iter()
69                    .map(|Point(x, y)| (x, y))
70                    .collect::<Vec<_>>();
71                if points[0] > points[1] {
72                    points.swap(0, 1);
73                }
74                sc.write(format!(
75                    "{} {} {} {}\n",
76                    points[0].0, points[0].1, points[1].0, points[1].1
77                ));
78            },
79            |expected, actual| {
80                assert!((expected.read::<f64>() - actual.read::<f64>()).abs() < 1e-6);
81                assert!((expected.read::<f64>() - actual.read::<f64>()).abs() < 1e-6);
82                assert!((expected.read::<f64>() - actual.read::<f64>()).abs() < 1e-6);
83                assert!((expected.read::<f64>() - actual.read::<f64>()).abs() < 1e-6);
84            },
85        );
86    }
87}
competitive_programming_rs/geometry/circle.rs

competitive_programming_rs/geometry/
circle.rs
