1264 线段相交
给出平面上两条线段的两个端点，判断这两条线段是否相交（有一个公共点或有部分重合认为相交）。 如果相交，输出"Yes"，否则输出"No"。
输入
第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)
输出
输出共T行，如果相交输出"Yes"，否则输出"No"。
输入样例
2
1 2 2 1 0 0 2 2
-1 1 1 1 0 0 1 -1
输出样例
Yes
No注意这个题中，部分重合可以算是线段相交。和nyoj1016类似 https://www.cnblogs.com/Weixu-Liu/p/10599278.htmlC++代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Point{
double x1,y1,x2,y2;
}point[2];
int cmp(
const Point& a,
const Point&
b){
double k1 = (a.x2 - a.x1)*(b.y1 - a.y1) - (b.x1 - a.x1)*(a.y2 -
a.y1);
double k2 = (a.x2 - a.x1)*(b.y2 - a.y1) - (b.x2 - a.x1)*(a.y2 -
a.y1);
if(k1 * k2 <=
0){
return true;
}
else{
return false;
}
}
int main(){
int T;
scanf("%d",&
T);
while(T--
){
scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&point[
0].x1,&point[
0].y1,&point[
0].x2,
&point[
0].y2,&point[
1].x1,&point[
1].y1,
&point[
1].x2,&point[
1].y2);
if(!(max(point[
0].x1,point[
0].x2) < min(point[
1].x1,point[
1].x2) ||
max(point[0].y1,point[
0].y2) < min(point[
1].y1,point[
1].y2) ||
max(point[1].x1,point[
1].x2) < min(point[
0].x1,point[
0].x2) ||
max(point[1].y1,point[
1].y2) < min(point[
0].y1,point[
0].y2))){
if(cmp(point[
0],point[
1]) && cmp(point[
1],point[
0])){
printf("Yes\n");
}
else{
printf("No\n");
}
}
else{
printf("No\n");
}
}
return 0;
}
请使用手机"扫一扫"x
转载于:https://www.cnblogs.com/Weixu-Liu/p/10599336.html
