首页 > 代码库 > 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——线段相关