51Nod 1264 线段相交(计算几何)

1264 线段相交 51Nod 1264 线段相交(计算几何)

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

51Nod 1264 线段相交(计算几何) 收藏

51Nod 1264 线段相交(计算几何) 关注

给出平面上两条线段的两个端点,判断这两条线段是否相交(有一个公共点或有部分重合认为相交)。 如果相交,输出"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示例

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

Output示例

Yes
No

题解:

        首先把两端点横纵坐标包围区域不重合的情况排除,剩下的情况用向量叉乘判断两线段是否相交(原理:根据右手定则,  ac×ab的方向与ad×ab的方向不一致时c点和d点在ab的两边(同向法),从而符合两线段有交点的条件)

 #include<iostream>
#include<string.h>
using namespace std;
struct node{
double x,y;
};
int main()
{
int T;
scanf("%d",&T);
node a,b,c,d;
double acb,adb,cad,cbd;
while(T--)
{
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y,&d.x,&d.y);
if(!(min(a.x,b.x)>max(c.x,d.x)||min(a.y,b.y)>max(c.y,d.y)||max(a.x,b.x)<min(c.x,d.x)||max(a.y,b.y)<min(c.y,d.y)))
{
acb=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);//ac×ab(ac.x*ab.y-ab.x*ac.y);
adb=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);//ad×ac
cad=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);//ca×cd
cbd=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);//cb×cd
if(acb*adb<=0&&cad*cbd<=0){//a,b在cd两边且c,d在a,b两边
printf("Yes\n");
continue;
}
}
printf("No\n");
}
return 0;
}
上一篇:Android Studio 快捷键(转)


下一篇:安卓工作室Android Studio 快捷键