本文主要是介绍线段交点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
线段交点
题目描述：
给定N个线段。求线段交点数。
保证没有两条线段共线
输入：
一行一个整数N，表示线段的个数
第2~N+1行，每行四个实数，x1,y1,x2,y2，表示线段的两个端点(x1,y1)和(x2,y2)
输出：
一行一个整数，表示线段交点数。
样例输入1：
3
0.00 0.00 1.00 1.00
0.00 1.00 1.00 0.00
0.00 0.00 1.00 0.00
样例输出1：
3
样例输入2：
3
0.00 0.00 1.00 1.00
0.00 0.00 1.00 0.00
0.00 0.00 0.00 1.00
样例输出2：
1
（没错这就是上一个题改了一下，其实是我把之前题看错了做的解法，然后，emmm，改成这个题意，就OK了）
先把坐标都换成向量,然后计算交点。
double getCrossPointx(STU s1, STU s2)
{Point a;a.y=s2.y2-s2.y1;a.x=s2.x2-s2.x1;Point b;b.y=s1.y1-s2.y1;b.x=s1.x1-s2.x1;Point c;c.y=s1.y2-s2.y1;c.x=s1.x2-s2.x1;double d1 = fabs(waiji(a, b));double d2 = fabs(waiji(a, c));double t = d1 / (d1 + d2);return 1.0*s1.x1 + (s1.x2 - s1.x1) * t;
}
double getCrossPointy(STU s1, STU s2)
{Point a;a.y=s2.y2-s2.y1;a.x=s2.x2-s2.x1;Point b;b.y=s1.y1-s2.y1;b.x=s1.x1-s2.x1;Point c;c.y=s1.y2-s2.y1;c.x=s1.x2-s2.x1;double d1 = fabs(waiji(a, b));double d2 = fabs(waiji(a, c));double t = d1 / (d1 + d2);return 1.0*s1.y1 + (s1.y2 - s1.y1) * t;
}跟前面那个结合一下，就变成了这样：
#include<bits/stdc++.h>
using namespace std;
struct Point//向量
{double x;double y;
};
typedef struct
{double x1;double y1;double x2;double y2;Point p1;Point p2;
}STU;
double maxx(double a,double b)
{if(a>b) return a;else return b;
}
double minn(double a,double b)
{if(a>b) return b;else return a;
}
bool judge1(STU a,STU b)
{if(maxx(a.x1,a.x2)<minn(b.x1,b.x2)||maxx(a.y1,a.y2)<minn(b.y1,b.y2)||minn(a.x1,a.x2)>maxx(b.x1,b.x2)||minn(a.y1,a.y2)>maxx(b.y1,b.y2)){return false;}else return true;
}
bool judge2(STU a,STU b)
{if((1.0*(a.x1-b.x1)*(b.y2-b.y1)-1.0*(a.y1-b.y1)*(b.x2-b.x1))*(1.0*(a.x2-b.x1)*(b.y2-b.y1)-1.0*(a.y2-b.y1)*(b.x2-b.x1))>0.000001){return false;}else if((1.0*(b.x1-a.x1)*(a.y2-a.y1)-1.0*(b.y1-a.y1)*(a.x2-a.x1))*(1.0*(b.x2-a.x1)*(a.y2-a.y1)-1.0*(b.y2-a.y1)*(a.x2-a.x1))>0.000001){return false;}else return true;
}
bool xiangjiao(STU a,STU b)
{if(!judge1(a,b)) return false;else if(!judge2(a,b)) return false;else return true;
}
double waiji(Point a, Point b)
{return 1.0*a.x*b.y - a.y*b.x;
}
double getCrossPointx(STU s1, STU s2)//求交点横坐标
{Point a;a.y=s2.y2-s2.y1;a.x=s2.x2-s2.x1;Point b;b.y=s1.y1-s2.y1;b.x=s1.x1-s2.x1;Point c;c.y=s1.y2-s2.y1;c.x=s1.x2-s2.x1;double d1 = fabs(waiji(a, b));double d2 = fabs(waiji(a, c));double t = d1 / (d1 + d2);return 1.0*s1.x1 + (s1.x2 - s1.x1) * t;
}
double getCrossPointy(STU s1, STU s2)//求交点纵坐标
{Point a;a.y=s2.y2-s2.y1;a.x=s2.x2-s2.x1;Point b;b.y=s1.y1-s2.y1;b.x=s1.x1-s2.x1;Point c;c.y=s1.y2-s2.y1;c.x=s1.x2-s2.x1;double d1 = fabs(waiji(a, b));double d2 = fabs(waiji(a, c));double t = d1 / (d1 + d2);return 1.0*s1.y1 + (s1.y2 - s1.y1) * t;
}
int main()
{int n,sum=0;cin>>n;STU stu[n+1];for(int i=1;i<=n;i++){scanf("%lf%lf%lf%lf",&stu[i].x1,&stu[i].y1,&stu[i].x2,&stu[i].y2);stu[i].p1.x=stu[i].x1;stu[i].p1.y=stu[i].y1;stu[i].p2.x=stu[i].x2;stu[i].p2.y=stu[i].y2;}int u=0,v=0;Point po[100000];for(int i=1;i<n;i++){for(int j=i+1;j<=n;j++){if(xiangjiao(stu[i],stu[j])) sum++;Point p;p.x=getCrossPointx(stu[i],stu[j]);p.y=getCrossPointy(stu[i],stu[j]);for(int k=0;k<u;k++)//判断是否重复{if(p.x==po[k].x&&p.y==po[k].y){v=1;break;}}if(v==0){po[u].x=p.x;po[u].y=p.y;u++;}else sum--;//重复，则不应该+1，但前面已经加了，故在此处减去}}printf("%d\n",sum);return 0;
}这篇关于线段交点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
