判断线段是否相交

连续线段的左转和右转的问题

连续线段的左转和右转

上图分别代表 左转(<0) 右转(>0)

根据这个性质可以判断点C是在线段AB的左边还是右边,这是判断两条线段是否相交的一个重要性质。

判断线段是否相交

线段相交的两种情况

如果\((\underset{AB}{\rightarrow}\times \underset{AC}{\rightarrow}\:)\, \ast\, (\underset{AB}{\rightarrow}\times \underset{AD}{\rightarrow}\: )\leq 0\)并且\((\underset{CD}{\rightarrow}\times \underset{CA}{\rightarrow}\:)\, \ast\, (\underset{CD}{\rightarrow}\times \underset{CB}{\rightarrow}\: )\leq 0\)那么线段AB和线段CD相交。

关于有向面积的计算

设有三角形ABC面积为A

则有:

有向面积计算

很遗憾,这个行列式MathJax貌似不支持,或者我没有get正确方法?

如果A>0,有向面积为正,ABC为逆时针排列;

如果A<0,ABC为顺时针排列。

所以具体来说,就是有向面积计算函数可以这么写:

1
2
3
4
double cal(Point a,Point b,Point c)
{
return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);//化简一下就跟上面辣个差不多啦
}

判断函数代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int check(Point a,Point b,Point c,Point d)
{
if(min(a.x,b.x)>max(c.x,d.x)||min(c.x,d.x)>max(a.x,b.x)
||min(a.y,b.y)>max(c.y,d.y)||min(c.y,d.y)>max(a.y,b.y))
return 0;
//先简单筛一下,防止(0,0)(1,1)/(2,2)(3,3)这种
double d1,d2,d3,d4;
d1 = cal(a,b,c);
d2 = cal(a,b,d);
d3 = cal(c,d,a);
d4 = cal(c,d,b);
if(d1*d2<=0&&d3*d4<=0) return 1;
else return 0;
}

完整代码

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
#include<iostream>
using namespace std;
typedef struct
{
double x,y;
} Point;
double cal(Point a,Point b,Point c)
{
return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
}
int check(Point a,Point b,Point c,Point d)
{
if(min(a.x,b.x)>max(c.x,d.x)||min(c.x,d.x)>max(a.x,b.x)
||min(a.y,b.y)>max(c.y,d.y)||min(c.y,d.y)>max(a.y,b.y))
return 0;
//先简单筛一下,防止(0,0)(1,1)/(2,2)(3,3)这种
double d1,d2,d3,d4;
d1 = cal(a,b,c);
d2 = cal(a,b,d);
d3 = cal(c,d,a);
d4 = cal(c,d,b);
if(d1*d2<=0&&d3*d4<=0) return 1;
else return 0;
}
int main(void)
{
Point p1,p2,p3,p4;
cin>>p1.x>>p1.y>>p2.x>>p2.y;
cin>>p3.x>>p3.y>>p4.x>>p4.y;
if(check(p1,p2,p3,p4)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}

相关题目

哈理工OJ 1559 Code 纯粹的裸题

HDU 1147 Code 这道题做得想哭,一直TLE (开了加速),最后把cin全部换成scanf瞬间过了…

HDU 1086 Code 比上面那道更水。

HDU 2150 Code 简单题,变成了折线