首页 > 代码库 > HDU 1086You can Solve a Geometry Problem too(判断两条选段是否有交点）
HDU 1086You can Solve a Geometry Problem too(判断两条选段是否有交点）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1086
判断两条线段是否有交点，我用的是跨立实验法：
两条线段分别是A1到B1，A2到B2，很显然，如果这两条线段有交点，那么可以肯定的是：
A1-B1,A2-B1这两个向量分别在B2-B1的两边，判断是不是在两边可以用向量的叉积来判断，这里就不说了，同理B1-A1,B2-A1在A2-A1的两边，当同时满足这两个条件时，说明这两条线段是有交点的。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 using namespace std; 7 const int maxn = 105; 8 const double eps = 1e-6; 9 struct point10 {11 double x,y;12 point(double x = 0,double y = 0):x(x),y(y) {}13 inline friend point operator + (point p1,point p2)14 {15 return point(p1.x+p2.x,p1.y+p2.y);16 }17 inline friend point operator - (point p1,point p2)18 {19 return point(p1.x-p2.x,p1.y-p2.y);20 }21 }A[maxn],B[maxn];22 23 inline double dot(point p1,point p2)24 {25 return p1.x*p2.y - p2.x*p1.y;26 }27 inline double dis(point p1,point p2)28 {29 return sqrt((p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y));30 }31 int judge(point p1,point p2,point p3,point p4)32 {33 double temp = dot(p3-p1,p2-p1) * dot(p4-p1,p2-p1);34 if(temp < 0 || fabs(temp) < eps) return 1;35 return 0;36 }37 38 int main()39 {40 //freopen("in","r",stdin);41 int n;42 while(scanf("%d",&n),n)43 {44 for(int i = 0;i < n;++i)45 scanf("%lf%lf%lf%lf",&A[i].x,&A[i].y,&B[i].x,&B[i].y);46 int ans = 0;47 for(int i = 0;i < n;++i)48 for(int j = i+1;j < n;++j)49 {50 if(judge(A[i],B[i],A[j],B[j]) && judge(A[j],B[j],A[i],B[i])) ans++;51 }52 printf("%d\n",ans);53 }54 return 0;55 }
HDU 1086You can Solve a Geometry Problem too(判断两条选段是否有交点）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。