51nod 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

判断两线段是否相交，用到向量叉积，如果说一条边的两个点在另一条边不同侧，另一条边的两个点也在这个边的两侧，那么肯定相交。
叉积符号不同说明在不同侧。数据水。
代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define eps 1e-6
#define MAX 101
using namespace std;
typedef pair<double,double> pa;
int t;
pa a,b,c,d;
double xm(pa a,pa b,pa c) {///求叉积
    return (b.first - a.first) * (c.second - b.second) - (b.second - a.second) * (c.first - b.first);
}
int main() {
    scanf("%d",&t);
    while(t --) {
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.first,&a.second,&b.first,&b.second,&c.first,&c.second,&d.first,&d.second);
        if(xm(a,c,d) * xm(b,c,d) <= 0 && xm(c,a,b) * xm(d,a,b) <= 0) printf("Yes
");///等于0说明点在线上
        else printf("No
");
    }
}