【51Nod】1264 - 线段相交（计算几何）

第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

/* (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>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
struct node
{
	double x,y;
};
bool check(node &a,node &b,node &c,node &d)		//检测ab跨立cd 
{
	double t1,t2;
	t1 = (a.x - c.x) * (d.y - c.y) - (a.y - c.y) * (d.x - c.x);
	t2 = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
	if (t1 * t2 >= 0)
		return true;
	return false;
}
bool solve(node &a,node &b,node &c,node &d)
{
	if (!check(a,b,c,d))
		return false;
	if (!check(c,d,a,b))
		return false;
	return true;
}
int main()
{
	int u;
	scanf ("%d",&u);
	while (u--)
	{
		node 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 (solve(a,b,c,d))		//跨立试验 
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}