51Nod－1264－线段相交【两线段相交的判定】

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.****.net/keyboarderqq/article/details/51222441)

#include <stdio.h> 

struct node  
{  
    double x;
    double y;  
}p[4];  

double f(struct node a,struct node b,struct node c)  
{  
    return a.x*b.y + c.x*a.y + b.x*c.y - c.x*b.y - a.x*c.y - b.x*a.y;  
}  
int main()  
{  
    int T;  
    scanf("%d",&T);  
    while(T--)  
    {  
        for(int i=0;i<4;i++)  
        {  
            scanf("%lf%lf",&p[i].x,&p[i].y);  
        }  
        double x1=f(p[0],p[2],p[3]);   
        double x2=f(p[3],p[2],p[1]);  
        double x3=f(p[2],p[0],p[1]);  
        double x4=f(p[1],p[0],p[3]);  
        if(x1*x2>=0 && x3*x4>=0)  
        {  
            printf("Yes\n");  
        }  
        else  
        {  
            printf("No\n");  
        }  
    }  
    return 0;  
}