1264 线段相交(计算几何)

基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

给出平面上两条线段的两个端点,判断这两条线段是否相交(有一个公共点或有部分重合认为相交)。 如果相交,输出”Yes”,否则输出”No”。

Input

第1行:一个数T,表示输入的测试数量(1 <= T <= 1000)
第2 - T + 1行:每行8个数,x1,y1,x2,y2,x3,y3,x4,y4。(-10^8 <= xi, yi <= 10^8)
(直线1的两个端点为x1,y1 | x2, y2,直线2的两个端点为x3,y3 | x4, y4)

Output

输出共T行,如果相交输出”Yes”,否则输出”No”。

Input示例

1
2
3
2
1 2 2 1 0 0 2 2
-1 1 1 1 0 0 1 -1

Output示例

1
2
Yes
No

题解:

计算几何判断线段相交模版

注释掉的部分是不包括端点和线段重合的模版

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cmath>
#include <list>
#include <vector>
using namespace std;

#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point{
double x,y,z;
}q[4];
//叉积
double xmult(point p1,point p2,point p0){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
//判三点共线
int dots_inline(point p1,point p2,point p3){
return zero(xmult(p1,p2,p3));
}
//判点是否在线段上,包括端点
int dot_online_in(point p,point l1,point l2){
return zero(xmult(p,l1,l2)&&(l1.x-p.x)*(l2.x-p.x)<eps&&(l1.y-p.y)*(l2.y-p.y)<eps);
}
//判两点在线段同侧,点在线段上返回0
int same_side(point p1,point p2,point l1,point l2){
return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;
}
//判两线段相交,包括端点和重合(p14)
int intersect_in(point u1,point u2,point v1,point v2){
if(!dots_inline(u1,u2,v1)||!dots_inline(u1,u2,v2))
return !same_side(u1,u2,v1,v2)&&!same_side(v1,v2,u1,u2);
return (dot_online_in(u1,v1,v2)||dot_online_in(u2,v1,v2)||
dot_online_in(v1,u1,u2)||dot_online_in(v2,u1,u2));
}
/*
//判两点在线段异侧
int opposite_side(point p1,point p2,point l1,point l2){
return xmult(l1,p1,l2)*xmult(l1,p2,l2)<-eps;
}
//判两线段相交,不包括端点和重合
int intersect_ex(point u1,point u2,point v1,point v2){
return opposite_side(u1,u2,v1,v2)&&opposite_side(v1,v2,u1,u2);
}
*/
int main(){
int t;
scanf("%d",&t);
while(t--){
for(int i=0;i<4;i++)scanf("%lf%lf",&q[i].x,&q[i].y);
if(intersect_in(q[0],q[1],q[2],q[3]))puts("Yes");
else puts("No");
}
return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2018-2021 LeFlacon

奶茶一杯 快乐起飞

支付宝
微信