HDU1086判断线段相交

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include<cassert>
 11 #include<set>
 12 using namespace std ;
 13 #ifdef DeBUG
 14 #define bug assert
 15 #else
 16 #define bug //
 17 #endif
 18 #define eps 1e-6
 19 struct segment
 20 {
 21     double xs;
 22     double ys;
 23     double xe;
 24     double ye;
 25 };
 26 bool isintersect(segment s1,segment s2)
 27 {
 28     //有公共顶点判断 
 29     if((s1.xs==s2.xs&&s1.ys==s2.ys)||(s1.xs==s2.xe&&s1.ys==s2.ye)||(s1.xe==s2.xs&&s1.ye==s2.ys)||(s1.xe==s2.xe&&s1.ye==s2.ye))
 30     return true;
 31     //叉乘判断相交 
 32     double angle1=(s2.xs-s2.xe)*(s1.ys-s2.ye)-(s1.xs-s2.xe)*(s2.ys-s2.ye);
 33     double angle2=(s2.xs-s2.xe)*(s1.ye-s2.ye)-(s2.ys-s2.ye)*(s1.xe-s2.xe);
 34     if(angle1*angle2<0)
 35     {
 36         double angle3=(s1.xs-s1.xe)*(s2.ye-s1.ye)-(s2.xe-s1.xe)*(s1.ys-s1.ye);
 37         double angle4=(s1.xs-s1.xe)*(s2.ys-s1.ye)-(s1.ys-s1.ye)*(s2.xs-s1.xe);
 38         if(angle4>-eps&&angle4<eps) 
 39         {
 40             if(s2.xs>=min(s1.xe,s1.xs)&&s2.xs<=max(s1.xe,s1.xs)&&s2.ys>=min(s1.ye,s1.ys)&&s2.ys<=max(s1.ye,s1.ys))
 41             return true;
 42             else
 43             return false;
 44         }
 45         else if(angle3>-eps&&angle3<eps)
 46         {
 47             if(s2.xe>=min(s1.xe,s1.xs)&&s2.xe<=max(s1.xe,s1.xs)&&s2.ye>=min(s1.ye,s1.ys)&&s2.ye<=max(s1.ye,s1.ys))
 48             return true;
 49             else
 50             return false;
 51         }
 52         else if(angle3*angle4<0)
 53         return true;
 54         else
 55         return false;
 56     }
 57     else if(angle1>-eps&&angle1<eps) 
 58     {
 59         if(s1.xs>=min(s2.xe,s2.xs)&&s1.xs<=max(s2.xe,s2.xs)&&s1.ys>=min(s2.ye,s2.ys)&&s1.ys<=max(s2.ye,s2.ys))
 60         return true;
 61         else
 62         return false;
 63     }
 64     else if(angle2>-eps&&angle2<eps)
 65     {
 66         if(s1.xe>=min(s2.xe,s2.xs)&&s1.xe<=max(s2.xe,s2.xs)&&s1.ye>=min(s2.ye,s2.ys)&&s1.ye<=max(s2.ye,s2.ys))
 67         return true;
 68         else
 69         return false;
 70     }
 71     else
 72     return false;
 73 }
 74 int main()
 75 {
 76     #ifdef DeBUG
 77         freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
 78     #endif
 79     
 80     int n;
 81     while(scanf("%d",&n),n)
 82     {
 83         int i,j,k;
 84         segment d[101];
 85         int cnt=0;
 86         for(i=0;i<n;i++)
 87         {
 88             scanf("%lf%lf%lf%lf",&d[i].xs,&d[i].ys,&d[i].xe,&d[i].ye);
 89         }
 90         for(i=0;i<n;i++)
 91         {
 92             for(j=i+1;j<n;j++)
 93             {
 94 
 95                     if(isintersect(d[i],d[j]))
 96                     cnt++;
 97             }
 98         }
 99         printf("%d
",cnt);
100     }
101     return 0;
102 }
View Code

原创代码，可做模板，上万数据测试通过

关于那几个angle注释，当angle为0时判断点是否在另一条线段上，如angle1=0,s1s是否在s2上

 

添加求交点函数

补充一个求交点的题

F - Intersecting Lines
Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u

Description

We all know that a pair of distinct points on a plane defines a line and that a pair of lines on a plane will intersect in one of three ways: 1) no intersection because they are parallel, 2) intersect in a line because they are on top of one another (i.e. they are the same line), 3) intersect in a point. In this problem you will use your algebraic knowledge to create a program that determines how and where two lines intersect.  Your program will repeatedly read in four points that define two lines in the x-y plane and determine how and where the lines intersect. All numbers required by this problem will be reasonable, say between -1000 and 1000. 

Input

The first line contains an integer N between 1 and 10 describing how many pairs of lines are represented. The next N lines will each contain eight integers. These integers represent the coordinates of four points on the plane in the order x1y1x2y2x3y3x4y4. Thus each of these input lines represents two lines on the plane: the line through (x1,y1) and (x2,y2) and the line through (x3,y3) and (x4,y4). The point (x1,y1) is always distinct from (x2,y2). Likewise with (x3,y3) and (x4,y4).

Output

There should be N+2 lines of output. The first line of output should read INTERSECTING LINES OUTPUT. There will then be one line of output for each pair of planar lines represented by a line of input, describing how the lines intersect: none, line, or point. If the intersection is a point then your program should output the x and y coordinates of the point, correct to two decimal places. The final line of output should read "END OF OUTPUT".

Sample Input

5
0 0 4 4 0 4 4 0
5 0 7 6 1 0 2 3
5 0 7 6 3 -6 4 -3
2 0 2 27 1 5 18 5
0 3 4 0 1 2 2 5

Sample Output

INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT
  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include<cassert>
 11 #include<set>
 12 using namespace std ;
 13 #ifdef DeBUG
 14 #define bug assert
 15 #else
 16 #define bug //
 17 #endif
 18 #define eps 1e-6
 19 struct segment
 20 {
 21     double xs;
 22     double ys;
 23     double xe;
 24     double ye;
 25 };
 26 double interx(segment s1,segment s2)
 27 {
 28     double a,b,c,d;
 29     a=s1.xe-s1.xs ;
 30     b=s1.ye-s1.ys ;
 31     c=s2.xe-s2.xs ;
 32     d=s2.ye-s2.ys ;
 33     if(a*d==b*c)
 34     {
 35         if((s2.xs-s1.xs)*b==(s2.ys-s1.ys)*a)
 36             return -1;//共线
 37         else return 0;//无交点
 38     }
 39     double x0=(a*d*s2.xs-b*c*s1.xs+a*c*s1.ys-a*c*s2.ys)/(a*d-b*c);
 40     return x0;
 41 }
 42 double intery(segment s1,segment s2)
 43 {
 44     double a,b,c,d;
 45     a=s1.xe-s1.xs ;
 46     b=s1.ye-s1.ys ;
 47     c=s2.xe-s2.xs ;
 48     d=s2.ye-s2.ys ;
 49     if(a*d==b*c)
 50     {
 51         if((s2.xs-s1.xs)*b==(s2.ys-s1.ys)*a)
 52             return -1;//共线
 53         else return 0;//无交点
 54     }
 55     double  y0=(a*d*s1.ys-b*c*s2.ys+b*d*s2.xs-b*d*s1.xs)/(a*d-b*c);
 56     return y0;
 57 }
 58 bool isintersect(segment s1,segment s2)
 59 {
 60     //有公共顶点判断 
 61     if((s1.xs==s2.xs&&s1.ys==s2.ys)||(s1.xs==s2.xe&&s1.ys==s2.ye)||(s1.xe==s2.xs&&s1.ye==s2.ys)||(s1.xe==s2.xe&&s1.ye==s2.ye))
 62     return true;
 63     //叉乘判断相交 
 64     double angle1=(s2.xs-s2.xe)*(s1.ys-s2.ye)-(s1.xs-s2.xe)*(s2.ys-s2.ye);
 65     double angle2=(s2.xs-s2.xe)*(s1.ye-s2.ye)-(s2.ys-s2.ye)*(s1.xe-s2.xe);
 66     if(angle1*angle2<0)
 67     {
 68         double angle3=(s1.xs-s1.xe)*(s2.ye-s1.ye)-(s2.xe-s1.xe)*(s1.ys-s1.ye);
 69         double angle4=(s1.xs-s1.xe)*(s2.ys-s1.ye)-(s1.ys-s1.ye)*(s2.xs-s1.xe);
 70         if(angle4>-eps&&angle4<eps) 
 71         {
 72             if(s2.xs>=min(s1.xe,s1.xs)&&s2.xs<=max(s1.xe,s1.xs)&&s2.ys>=min(s1.ye,s1.ys)&&s2.ys<=max(s1.ye,s1.ys))
 73             return true;
 74             else
 75             return false;
 76         }
 77         else if(angle3>-eps&&angle3<eps)
 78         {
 79             if(s2.xe>=min(s1.xe,s1.xs)&&s2.xe<=max(s1.xe,s1.xs)&&s2.ye>=min(s1.ye,s1.ys)&&s2.ye<=max(s1.ye,s1.ys))
 80             return true;
 81             else
 82             return false;
 83         }
 84         else if(angle3*angle4<0)
 85         return true;
 86         else
 87         return false;
 88     }
 89     else if(angle1>-eps&&angle1<eps) 
 90     {
 91         if(s1.xs>=min(s2.xe,s2.xs)&&s1.xs<=max(s2.xe,s2.xs)&&s1.ys>=min(s2.ye,s2.ys)&&s1.ys<=max(s2.ye,s2.ys))
 92         return true;
 93         else
 94         return false;
 95     }
 96     else if(angle2>-eps&&angle2<eps)
 97     {
 98         if(s1.xe>=min(s2.xe,s2.xs)&&s1.xe<=max(s2.xe,s2.xs)&&s1.ye>=min(s2.ye,s2.ys)&&s1.ye<=max(s2.ye,s2.ys))
 99         return true;
100         else
101         return false;
102     }
103     else
104     return false;
105 }
106 int main()
107 {
108     #ifdef DeBUG
109         freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
110     #endif
111     
112     int n;
113     printf("INTERSECTING LINES OUTPUT
");
114     while(scanf("%d",&n)!=EOF)
115     {
116         int i,j,k;
117         segment d[101];
118         segment s1,s2;
119         int cnt=0;
120         for(i=0;i<n;i++)
121         {
122             scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&s1.xs,&s1.ys,&s1.xe,&s1.ye,&s2.xs,&s2.ys,&s2.xe,&s2.ye);
123                     if(interx(s1,s2)==-1)
124                     {
125                         printf("LINE
");
126                     } 
127                     else if(interx(s1,s2)==0)
128                     {
129                         printf("NONE
");
130                     }
131                     else
132                     {
133                         printf("POINT %.2lf %.2lf
",interx(s1,s2),intery(s1,s2));
134                     }
135         }
136     }
137     printf("END OF OUTPUT
");
138     return 0;
139 }
View Code

 这个版也可以

对应POJ 2653 Pick-up sticks

 1 #include<stdio.h>
 2 #include<time.h>
 3 struct point
 4 {
 5     double x,y;
 6 };
 7 struct stick
 8 {
 9     point u,v;
10 }s[100005];
11 double cross(point &a, point &b, point &o)
12 {
13     return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
14 }
15 double min(double &a, double &b)
16 {
17     return a<b?a:b;
18 }
19 double max(double &a, double &b)
20 {
21     return a>b?a:b;
22 }
23 bool quick(stick &a, stick &b)
24 {
25     return max(a.u.x, a.v.x)>min(b.u.x, b.v.x) and max(a.u.y, a.v.y)>min(b.u.y, b.v.y) and max(b.u.x, b.v.x)>min(a.u.x, a.v.x) and max(b.u.y, b.v.y)>min(a.u.y, a.v.y);
26 }
27 bool check(stick &a, stick &b)
28 {
29     if(quick(a,b))
30     {
31         return cross(a.u,b.u,b.v)*cross(a.v,b.u,b.v)<-1e-8 and cross(b.u,a.u,a.v)*cross(b.v,a.u,a.v)<-1e-8;
32     }
33     return false;
34 }
35         int is[100002]={0};
36 int main()
37 {
38 //    freopen("C:\Users\Sky\Desktop\1.in","r",stdin);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
39     int n;
40     int i,j;
41     while(scanf("%d",&n),n)
42     {
43         for(i=1;i<=n;i++)
44         {
45             scanf("%lf%lf%lf%lf",&s[i].u.x,&s[i].u.y,&s[i].v.x,&s[i].v.y);
46             is[i]=1;
47             for(j=1;j<i;j++)
48             {
49                 if(is[j])
50                 {
51                     if(check(s[i],s[j]))
52                     is[j]=0;
53                 }
54             }
55         }
56    
57         int _flag=1;
58         for(i=1;i<=n;i++)
59         {
60             if(is[i])
61             {
62                 if(_flag==1)
63                 {
64                     _flag=0;
65                     printf("Top sticks: %d",i);
66                     continue;
67                 }
68                 else
69                 printf(", %d",i);
70             }
71         }
72         printf(".
");
73         
74     }
75  //   printf("Time used = %.0lf ms
",(double)(1000*clock()/CLOCKS_PER_SEC));
76     return 0;
77 }
View Code

然后是我的版的应用于此题

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include <cassert>
 11 #include <set>
 12 #include <sstream>
 13 #include <map>
 14 using namespace std ;
 15 #ifdef DeBUG
 16 #define bug assert
 17 #else
 18 #define bug //
 19 #endif
 20 #define zero {0}
 21 #define eps 1e-6
 22 struct segment
 23 {
 24     double xs;
 25     double ys;
 26     double xe;
 27     double ye;
 28 };
 29 bool isintersect(segment s1,segment s2)
 30 {
 31     //有公共顶点判断 
 32     if((s1.xs==s2.xs&&s1.ys==s2.ys)||(s1.xs==s2.xe&&s1.ys==s2.ye)||(s1.xe==s2.xs&&s1.ye==s2.ys)||(s1.xe==s2.xe&&s1.ye==s2.ye))
 33     return true;
 34     //叉乘判断相交 
 35     double angle1=(s2.xs-s2.xe)*(s1.ys-s2.ye)-(s1.xs-s2.xe)*(s2.ys-s2.ye);
 36     double angle2=(s2.xs-s2.xe)*(s1.ye-s2.ye)-(s2.ys-s2.ye)*(s1.xe-s2.xe);
 37     if(angle1*angle2<0)
 38     {
 39         double angle3=(s1.xs-s1.xe)*(s2.ye-s1.ye)-(s2.xe-s1.xe)*(s1.ys-s1.ye);
 40         double angle4=(s1.xs-s1.xe)*(s2.ys-s1.ye)-(s1.ys-s1.ye)*(s2.xs-s1.xe);
 41         if(angle4>-eps&&angle4<eps) 
 42         {
 43             if(s2.xs>=min(s1.xe,s1.xs)&&s2.xs<=max(s1.xe,s1.xs)&&s2.ys>=min(s1.ye,s1.ys)&&s2.ys<=max(s1.ye,s1.ys))
 44             return true;
 45             else
 46             return false;
 47         }
 48         else if(angle3>-eps&&angle3<eps)
 49         {
 50             if(s2.xe>=min(s1.xe,s1.xs)&&s2.xe<=max(s1.xe,s1.xs)&&s2.ye>=min(s1.ye,s1.ys)&&s2.ye<=max(s1.ye,s1.ys))
 51             return true;
 52             else
 53             return false;
 54         }
 55         else if(angle3*angle4<0)
 56         return true;
 57         else
 58         return false;
 59     }
 60     else if(angle1>-eps&&angle1<eps) 
 61     {
 62         if(s1.xs>=min(s2.xe,s2.xs)&&s1.xs<=max(s2.xe,s2.xs)&&s1.ys>=min(s2.ye,s2.ys)&&s1.ys<=max(s2.ye,s2.ys))
 63         return true;
 64         else
 65         return false;
 66     }
 67     else if(angle2>-eps&&angle2<eps)
 68     {
 69         if(s1.xe>=min(s2.xe,s2.xs)&&s1.xe<=max(s2.xe,s2.xs)&&s1.ye>=min(s2.ye,s2.ys)&&s1.ye<=max(s2.ye,s2.ys))
 70         return true;
 71         else
 72         return false;
 73     }
 74     else
 75     return false;
 76 }
 77     segment a[100001];
 78     int is[100001];
 79 int main()
 80 {
 81     #ifdef DeBUG
 82         freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
 83     #endif
 84     int n;
 85     int i,j,k;
 86 
 87     while(scanf("%d",&n),n)
 88     {
 89         for(i=0;i<n;i++)
 90         {
 91             scanf("%lf %lf %lf %lf",&a[i].xs,&a[i].ys,&a[i].xe,&a[i].ye);
 92     is[i]=1;
 93     /*
 94             for(j=0;j<i;j++)//的确暴力需要技巧 
 95             if(is[j])
 96             {
 97                 if(isintersect(a[i],a[j]))
 98                 is[j]=0;
 99             }*/
100         }
101         for(i=0;i<n;i++)
102         {
103             for(j=i+1;j<n;j++)
104             {
105                 if(isintersect(a[i],a[j]))
106                 {
107                     is[i]=0;
108                     break;
109                 }
110             }
111         }
112         int _flag=1;
113         for(i=0;i<n;i++)
114         {
115             if(is[i])
116             {
117                 if(_flag==1)
118                 {
119                     _flag=0;
120                     printf("Top sticks: %d",i+1);
121                     continue;
122                 }
123                 else
124                 printf(", %d",i+1);
125             }
126         }
127         printf(".
");
128     }
129     
130     return 0;
131 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Skyxj/p/3186268.html