欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-03 21:07:33
...

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

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

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

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

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

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

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

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

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

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

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

如果同时满足上述两个条件,那么这个线段是不是就相交呢?(我是否讲的清清楚楚,明明白白的呢?)

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

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

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

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

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

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

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

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

两线段相交还有两种情况

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

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

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

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

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

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

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;
}

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