判断线段是否相交，HDU-1086

我们已经在上一节学习的如何判断两个线段的位置，就是两个线段的叉乘与0的关系

我们往下引申一下，知道了两个线段的关系后，你是否能判断两个线段相交呢？？？

先让你想两分钟，在纸上画一画。

好的，下面我就来讲下我自己的理解，如果有错，欢迎指出，大家一起进步。

我们已经能判断两个线段的位置了，那么我们能不能判断一个点和线段的位置呢？

上一节我们讲的p0p1和p0p2其实就是3个点，然后判断点p1相对与p0p2的位置，（现在再想一下怎么判断线段是否相交呢？）

看看这个图，再想一想，2个线段，4个点。

有没有一种恍然大悟的感觉？？？

你先以一个线段为基准，判断另外2个点的位置，是否在线段的两侧

然后再以另外两个2点连成的线段为基准，判断2个点的是否在这个线段的两侧

如果同时满足上述两个条件，那么这个线段是不是就相交呢？（我是否讲的清清楚楚，明明白白的呢？）

如果还是不够清楚，我来画张图

我们是不是要判断AB和CD呢？

之后用我们先以AB为基准，判断C点和D点相对线段AB的位置

然后再以线段CD为基准判断点A和点B的相对线段CD的位置。

如果满足上面两个条件，那么这两个线段就相交

两线段相交还有两种情况

如何判断是点C，点D在线段AB的两侧呢？

如何判断是点A，点B在线段CD的两侧呢？

这就用到了上节我们所学的叉乘。

是不是有点简单呢，我是否将清楚了呢？，下面上个题练一下，

HDU-1086

题目意思：

给出n个线段，判断这n条线段中，线段相交的对数

#include<bits/stdc++.h>
#include <stdio.h>
using namespace std;
int n;
struct node{
	double x1,y1,x2,y2;
}a[105]; 
bool solve(node a,node b){
	double u2,v2,w2,p2,q2,z2;
	double u1,v1,w1,p1,q1,z1;
	u1=a.x2-a.x1;//基准向量的x值
	v1=a.y2-a.y1;//基准向量的y值
	p1=b.x1-a.x1;
	q1=b.y1-a.y1;
	w1=b.x2-a.x1;
	z1=b.y2-a.y1;
	u2=b.x2-b.x1;//基准向量的x值
	v2=b.y2-b.y1;//基准向量的y值
	p2=a.x1-b.x1;
	q2=a.y1-b.y1;
	w2=a.x2-b.x1;
	z2=a.y2-b.y1;
	if(((u1*q1)-(v1*p1))*((u1*z1)-(v1*w1))>0)
	return false;
	else if(((u2*q2)-(v2*p2))*((u2*z2)-(v2*w2))>0)
	return false;
	
	return true;
}
int main(){
	while(scanf("%d",&n)&&n){
		int ans=0;
		for(int i=1;i<=n;i++){
			scanf("%lf%lf%lf%lf",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;j<=n;j++)
			{
				if(solve(a[i],a[j]))
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

这个如果直接写叉乘，会很头晕，所以尽量简化。