(一)问题2001年第10期擂台赛的问题是: 给定n条线段,请编一程序，给出所有的交点坐标。
(二)一般解法该问题的解决并不难: 遍历该组线段中的任意一对求出交点即可。具体两线段交点的求法为：(1)先对应两线段分别对它们所在的直线写出相应的两点式方程，即设一线段两端点坐标分别为(xi,yi)与(xj,yj),则对应直线方程为: (y-yi)/(x-xi)=(y-yj)/(x-xj);(2)求两直线交点坐标,即联合两直线方程得一个一元二次方程组，求解之；(3)如方程组有解,判断解是否在两线段的两端点之间或端点上。是则方程组之解即是两线段的交点;否则两线段无交点。当然,在求两线段交点前还可以用一些条件式加以过滤,如对两线段所对应矩形无相交部分的情况,可直接判断两线段无交点等等。
(三)编程实例参赛程序有许多采用了上述方法,这里选载一个比较典型的程序设计
/* 程序说明
程序中的几个变量:
*x1棗线段初始点横坐标*y1棗线段初始点纵坐标
*x2棗线段终止点横坐标*y2棗线段终止点纵坐标
*a棗线段所在直线解析式中x项系数*b棗线段所在直线解析式中y项系数
*c棗线段所在直线解析式中常数项jx棗两条线段所在直线交点横坐标
jy棗两条线段所在直线交点纵坐标程序结构:
读出变量， 分配内存。用解析几何中计算两直线交点的公式两两计算两条线段所在直线交点。
用函数between判断两条线段所在直线交点是否
在线段上，若是，则输出结果。*/
#include <stdio.h>
#include <stdlib.h>
// 此函数判断交点坐标是否在线段坐标范围内,即判断交点是否落在线段上
int between(float u, float v, float w)
{ float max,min;
max=(v>w)?v:w;
min=(v<w)?v:w;
return ((u<=max&&u>=min)?1:0);
}
int main()
{
int n,i,j,num; //n为线段条数
float x1[100],y1[100],x2[100],y2[100],a[100],b[100],c[100],jx,jy;
while(scanf("%d",&n)&&n!=0)
{
num=0;
for(i=0;i<n;++i)
{ scanf("%f%f%f%f",&x1[i],&y1[i],&x2[i],&y2[i]);
if(x1[i]==x2[i])
{
a[i]=1;b[i]=0;c[i]=-x1[i];
}
else
{
a[i]=(y2[i]-y1[i])/(x1[i]-x2[i]);b[i]=1;
c[i]=(x1[i]*y2[i]-x2[i]*y1[i])/(x2[i]-x1[i]);
}
}
for(i=0;i<n;++i)
{
for(j=i+1;j<n;++j)
{
if(a[i]*b[j]-a[j]*b[i]!=0)
{
jx=(b[i]*c[j]-b[j]*c[i])/(a[i]*b[j]-a[j]*b[i]);
jy=(c[i]*a[j]-c[j]*a[i])/(a[i]*b[j]-a[j]*b[i]);
if(between(jx,x1[i],x2[i])&&between(jx,x1[j],x2[j])&&between(jy,y1[i],y2[i])&&between(jy,y1[j],y2[j]))
//printf("(%f,%f)\n ",jx,jy);
num++;
}
}
}
printf("%d\n",num);
}
return 0;
}
(四)另一算法设计这里再给出一种求解算法。首先,对给定的n条边的2n个端点按X坐标由小到大的次序进行排序,并在每一端点处作一平行Y轴的辅助虚线。一个实例如图所示， 共有5条线段,分别编号为:第1,2..5 号线段,共2 × 5=10 个端点。对每一辅助线,将有一些线段与之相交,将能与之相交的边的序号按交点Y坐标由大到小排序,由上向下记录。例如，图中每条虚线下面对应记录的一组边序号：{1}，{1，2}，{2，1}，{2,3}..等。对两虚线,显然一对线段要相交的充分必要条件是在两虚线处对应边序号序列中两边序号都存在,且两边序号正好排序相反。例如: 图中:第1虚线{1}与第2虚线{1,2}没有共同两边序号,故其间无线段相交；第2虚线{1,2}与第3虚线{2,1}有共同两边序号1与2, 且第2虚线处排序为1->2, 第3虚线处排序为2->1,两者反序, 故其间线段2 必与线段3 相交；第3虚线{2,1}与第4虚线{2,3}没有共同两边序号,只有一个共同边序号2,故其间无线段相交；第4虚线{2,3}与第5虚线{2,3}虽有共同两边序号2与3, 但排序同为2->3,故其间无线段相交；第5虚线{2,3}与第6虚线{3,5}没有共同两边序号, 只有一个共同边序号3,故其间无线段相交；第6虚线{3,5}与第7虚线{4,3,5}虽有共同两边序号3与5, 但排序同为3->5,故其间无线段相交；第7虚线{4,3,5}与第8虚线{3,4,5}有共同三边序号3,4与5, 但排序不同的只有一对:3->4与4->3,故其间有一对线段3 与4 相交；第8虚线{3,4,5}与第9虚线{5,4}有共同两边序号4与5, 且第8虚线处排序为4->5, 第9虚线处排序为5->4,两者反序, 故其间线段4必与线段5相交；第9虚线{5,4}与第10虚线{4}没有共同两边序号,故其间无线段相交；由以上讨论可自然导出下列算法。
算法:(1)对n条线段的2n个端点按X坐标升序排序；
(2)依次给出每一端点Y坐标辅助虚线处按Y坐标排序的边序号序列;其中如两边Y坐标同,则直接判断在虚线处有相应交点；序列中边序列号的确定按X坐标从小到大,碰到左端点加相应边边序号,碰到右端点删去相应边边序号方法进行。
(3) 扫描每一虚线区间,如前后虚线处对应边序列共同边超过1 条,则遍查所有前后逆序线对，并求出交点坐标输出。
设A (Ax,Ay) B(Bx,By) C(Cx,Cy) D(Dx,Dy)四点坐标
#define Max(X,Y) (X)>=(Y)?(X):(Y);
#define Min(X,Y) (X)>=(Y)?(Y):(X);
只要 (Ax<=Max(Cx,Dx)&&Ax>=Min(Cx,Dx)) && (Bx<=Max(Cx,Dx)&&Bx>=Min(Cx,Dx))
就有交点
定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
|x1 x2 x3|
S(P1,P2,P3) = |y1 y2 y3| = (x1-x3)*(y2-y3) - (y1-y3)(x2-x3)
|1 1 1|
已知一条线段的两个端点为A(x1,y1),B(x2,y2),另一条线段的两个端点为C(x3,y3),D(x4,y4),要判断AB与CD是否有交点，若有求出.
首先判断d = (y2-y1)(x4-x3)-(y4-y3)(x2-x1)，
若d=0，则直线AB与CD平行或重合，
若d!=0，则直线AB与CD有交点，设交点为E(x0,y0)：
则有:CE/ED = S(A,C,B) / S(A,B,D)
所以:CE/CD = S(A,C,B) / (S(A,C,B) + S(A,B,D))
故 x0 = C.x + (D.x - C.x) * S(A,C,B) / (S(A,C,B) + S(A,B,D));
y0 = C.y + (D.y - C.y) * S(A,C,B) / (S(A,C,B) + S(A,B,D));
也可以直接求
x0 = [(x2-x1)*(x4-x3)*(y3-y1)+(y2-y1)*(x4-x3)*x1-(y4-y3)*(x2-x1)*x3]/d
y0 = [(y2-y1)*(y4-y3)*(x3-x1)+(x2-x1)*(y4-y3)*y1-(x4-x3)*(y2-y1)*y3]/(-d)
求出交点后在判断交点是否在线段上，即判断以下的式子：
(x0-x1)*(x0-x2)<=0
(x0-x3)*(x0-x4)<=0
(y0-y1)*(y0-y2)<=0
(y0-y3)*(y0-y4)<=0
只有上面的四个式子都成立才可判定(x0,y0)是线段AB与CD的交点，否则两线段无交点
