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