【模板】计算几何--线段相交问题

 1 #include<algorithm>
 2 #include<cmath>
 3 
 4 const double EPS=1e-10;
 5 
 6 //考虑误差的加法运算
 7 double add(double a,double b)
 8 {
 9     if(fabs(a+b)<EPS*(fabs(a)+fabs(b)))
10         return 0;
11     return a+b;
12 }
13 
14 //二维向量结构体
15 struct P
16 {
17     double x,y;
18 
19     //构造函数
20     P(){}
21     P(double x,double y):x(x),y(y){}
22 
23     //重载加法运算
24     P operator + (P p)
25     {
26         return P(add(x,p.x),add(y,p.y));
27     }
28 
29     //重载减法运算
30     P operator - (P p)
31     {
32         return P(add(x,-p.x),add(y,-p.y));
33     }
34 
35     //重载乘法运算
36     P operator * (double d)
37     {
38         return P(x*d,y*d);
39     }
40 
41     //向量内积
42     double dot(P p)
43     {
44         return add(x*p.x,y*p.y);
45     }
46 
47     //向量外积
48     double det(P p)
49     {
50         return add(x*p.y,-y*p.x);
51     }
52 };
53 
54 //判断点q是否在线段p1-p2上
55 bool on_seg(P p1,P p2,P q)
56 {
57     return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;
58 }
59 
60 //计算直线p1-p2与直线q1-q2的交点，使用前需判断两条直线是否平行（(p1-q1).det(p2-q2)==0表示两条直线平行）
61 P intersection(P p1,P p2,P q1,P q2)
62 {
63     return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));
64 }