首页 > 代码库 > NO9——线段相关
NO9——线段相关
1 #include <stdio.h> 2 #include <iostream> 3 #include <math.h> 4 #include <algorithm> 5 using namespace std; 6 7 struct point 8 { 9 double x,y; 10 }; 11 point a[105][2];//a[i][0]代表第i条线段的头,a[i][1]代表尾 12 13 double fan(double x,double y) 14 { 15 return x>y?x:y; 16 } 17 18 double fin(double c,double d) 19 { 20 return c<d?c:d; 21 } 22 23 double cnt(point a,point b) 24 { 25 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 26 } 27 28 int is(point a,point b,point c,point d) 29 { 30 if(a.x==b.x&&c.x==d.x) 31 { 32 return 0; 33 } 34 if(a.x==b.x&&c.x!=d.x) 35 { 36 double m1=a.x; 37 double m2=(a.x-c.x)*(d.y-c.y)/(d.x-c.x)+c.y; 38 if(m1<=fan(a.x,b.x)&&m1>=fin(a.x,b.x)&&m2>=fin(a.y,b.y)&&m2<=fan(a.y,b.y)&&m1<=fan(c.x,d.x)&&m1>=fin(c.x,d.x)&&m2>=fin(c.y,d.y)&&m2<=fan(c.y,d.y)) 39 return 1; 40 } 41 if(c.x==d.x&&a.x!=b.x) 42 { 43 double m1=c.x; 44 double m2=a.y+(b.y-a.y)*(c.x-a.x)/(b.x-a.x); 45 if(m1<=fan(a.x,b.x)&&m1>=fin(a.x,b.x)&&m2>=fin(a.y,b.y)&&m2<=fan(a.y,b.y)&&m1<=fan(c.x,d.x)&&m1>=fin(c.x,d.x)&&m2>=fin(c.y,d.y)&&m2<=fan(c.y,d.y)) 46 return 1; 47 } 48 double k1=(b.y-a.y)/(b.x-a.x); 49 double k2=(d.y-c.y)/(d.x-c.x); 50 double m1,m2,x,y; 51 if(k1==k2) return 0; 52 else 53 { 54 m1=a.y-k1*a.x; 55 m2=c.y-k2*c.x; 56 x=(m1-m2)/(k2-k1); 57 y=k1*x+m1; 58 if(x<=fan(a.x,b.x)&&x>=fin(a.x,b.x)&&y>=fin(a.y,b.y)&&y<=fan(a.y,b.y)&&x<=fan(c.x,d.x)&&x>=fin(c.x,d.x)&&y>=fin(c.y,d.y)&&y<=fan(c.y,d.y)) 59 return 1; 60 } 61 return 0; 62 } 63 64 int main() 65 { 66 int cas = 1; 67 int n,i,j; 68 while(~scanf("%d",&n),n) 69 { 70 int cnt = 0; 71 for(i = 0;i<n;i++) 72 scanf("%lf%lf%lf%lf",&a[i][0].x,&a[i][0].y,&a[i][1].x,&a[i][1].y);//线段的首尾坐标 73 for(i = 0;i<n;i++) 74 { 75 for(j = i+1;j<n;j++) 76 { 77 if(is(a[i][0],a[i][1],a[j][0],a[j][1])) 78 cnt++; 79 } 80 } 81 printf("%d\n",cnt); 82 } 83 84 return 0; 85 }
NO9——线段相关
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。