51nod1264线段相交

发表于 | 分类于 |

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示例
2
1 2 2 1 0 0 2 2
-1 1 1 1 0 0 1 -1
Output示例
Yes
No
做这到题首先要了解叉乘的概念~~http://blog.csdn.net/hustspy1990/article/details/11082745
然后还要知道两条线段相交的必要条件 http://dev.gameres.com/Program/Abstract/Geometry.htm#%E5%88%A4%E6%96%AD%E4%B8%A4%E7%BA%BF%E6%AE%B5%E6%98%AF%E5%90%A6%E7%9B%B8%E4%BA%A4

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
/*  (a-c)×(d-c)*(d-c)×(b-c)>=0&&(c-a)×(b-a)*(b-a)×(d-a)>= 0就可以判断ab,cd相交*/
/*  p1×p2 = x1y2 - x2y1 = - p2×p1-----（叉乘公式）*/
#include<stdio.h>
struct point
{
    double x,y;
};
//struct point a,b,c,d;
int mp(point a,point b,point c,point d){
    double C=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
    double D=(d.x-c.x)*(b.y-c.y)-(b.x-c.x)*(d.y-c.y);
    if(C*D<0) return 0;
    else return 1;
}
bool check(point a , point b , point c , point d){
    if(!mp(a,b,c,d)) return false;
    if(!mp(c,d,a,b)) return false;
    return true;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        point a,b,c,d;
        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(check(a,b,c,d))
            printf("Yes\n");
        else
             printf("No\n");
    }
}