判断两线段是否相交（快速排斥和跨立）
背景知识：
判断两线段是否相交：
我们分两步确定两条线段是否相交：
(1)快速排斥试验
设以线段 P1P2 为对角线的矩形为R，
设以线段 Q1Q2 为对角线的矩形为T，
如果R和T不相交，显然两线段不会相交。
(2)跨立试验
如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线，但是因为已经通过快速排斥试验，所以 P1 一定在线段 Q1Q2上；同理，( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是：( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是：( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示：
程序模版：
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
typedef struct line
{P s;P e;
}Line;
Line L[M];
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)//叉积
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)//跨立实验（通过相互跨立则可确定两线段相交返回1）
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
} 相关题目：
hdu1086 判断线段相交
You can Solve a Geometry Problem too
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 6740 Accepted Submission(s): 3256
Problem Description Many geometry（几何）problems were designed in the ACM/ICPC. And now, I also prepare a geometry problem for this final exam. According to the experience of many ACMers, geometry problems are always much trouble, but this problem is very easy, after all we are now attending an exam, not a contest :)
Give you N (1<=N<=100) segments（线段）, please output the number of all intersections（交点）. You should count repeatedly if M (M>2) segments intersect at the same point.
Note:
You can assume that two segments would not intersect at more than one point.
Input Input contains multiple test cases. Each test case contains a integer N (1=N<=100) in a line first, and then N lines follow. Each line describes one segment with four float values x1, y1, x2, y2 which are coordinates of the segment’s ending.
A test case starting with 0 terminates the input and this test case is not to be processed.
Output For each case, print the number of intersections, and one line one case.
Sample Input
2 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.00 3 0.00 0.00 1.00 1.00 0.00 1.00 1.00 0.000 0.00 0.00 1.00 0.00 0
Sample Output
1 3分析：判断交点数：
程序：
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
typedef struct line
{P s;P e;
}Line;
Line L[M];
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)//叉积
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)//跨立实验（通过相互跨立则可确定两线段相交返回1）
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
int main()
{int n,i,j;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);int cnt=0;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(paichi(L[i],L[j])&&kuali(L[i],L[j]))cnt++;}}printf("%d\n",cnt);}
}
题目：
Jack Straws
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 3066 | Accepted: 1376 |
Description
In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. Here, we are only concerned with if various pairs of straws are connected by a path of touching straws. You will be given a list of the endpoints for some straws (as if they were dumped on a large piece of graph paper) and then will be asked if various pairs of straws are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws.Input
Input consist multiple case,each case consists of multiple lines. The first line will be an integer n (1 < n < 13) giving the number of straws on the table. Each of the next n lines contain 4 positive integers,x1,y1,x2 and y2, giving the coordinates, (x1,y1),(x2,y2) of the endpoints of a single straw. All coordinates will be less than 100. (Note that the straws will be of varying lengths.) The first straw entered will be known as straw #1, the second as straw #2, and so on. The remaining lines of the current case(except for the final line) will each contain two positive integers, a and b, both between 1 and n, inclusive. You are to determine if straw a can be connected to straw b. When a = 0 = b, the current case is terminated.When n=0,the input is terminated.
There will be no illegal input and there are no zero-length straws.
Output
You should generate a line of output for each line containing a pair a and b, except the final line where a = 0 = b. The line should say simply "CONNECTED", if straw a is connected to straw b, or "NOT CONNECTED", if straw a is not connected to straw b. For our purposes, a straw is considered connected to itself.Sample Input
7 1 6 3 3 4 6 4 9 4 5 6 7 1 4 3 5 3 5 5 5 5 2 6 3 5 4 7 2 1 4 1 6 3 3 6 7 2 3 1 3 0 02 0 2 0 0 0 0 0 1 1 1 2 2 1 2 0 00
Sample Output
CONNECTED NOT CONNECTED CONNECTED CONNECTED NOT CONNECTED CONNECTED CONNECTED CONNECTED CONNECTED分析：判断线段相交+并查集
程序：
#include"stdio.h"
#include"string.h"
#include"math.h"
#include"stdlib.h"
#define M 101
#define inf 999999999
#define eps 1e-10
typedef struct node
{double x,y;
}P;
int f[M];
int finde(int x)
{if(x!=f[x])f[x]=finde(f[x]);return f[x];
}
void make(int a,int b)
{int x=finde(a);int y=finde(b);if(x!=y)f[x]=y;
}
double max(double x,double y)
{return x>y?x:y;
}
double min(double x,double y)
{return x=min(b.s.x,b.e.x)&&max(b.s.x,b.e.x)>=min(a.s.x,a.e.x)&&max(a.s.y,a.e.y)>=min(b.s.y,b.e.y)&&max(b.s.y,b.e.y)>=min(a.s.y,a.e.y))return 1;elsereturn 0;
}
double cross(node a,node b,node c)
{double x1=b.x-a.x;double y1=b.y-a.y;double x2=c.x-a.x;double y2=c.y-a.y;return x1*y2-x2*y1;
}
int kuali(line a,line b)
{if(cross(a.s,a.e,b.s)*cross(a.s,a.e,b.e)<=0&&cross(b.s,b.e,a.s)*cross(b.s,b.e,a.e)<=0)return 1;return 0;
}
int main()
{int i,n,j;while(scanf("%d",&n),n){for(i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&L[i].s.x,&L[i].s.y,&L[i].e.x,&L[i].e.y);for(i=1;i<=n;i++)f[i]=i;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){if(paichi(L[i],L[j])&&kuali(L[i],L[j]))make(i,j);}}int a,b;while(scanf("%d%d",&a,&b),a||b){if(finde(a)==finde(b))printf("CONNECTED\n");elseprintf("NOT CONNECTED\n");}}return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！