原创代码，可做模板，上万数据测试通过
关于那几个angle注释，当angle为0时判断点是否在另一条线段上，如angle1=0,s1s是否在s2上
添加求交点函数
补充一个求交点的题
F - Intersecting Lines Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit StatusDescription
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 5Sample 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\n"); 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\n"); 126 } 127 else if(interx(s1,s2)==0) 128 { 129 printf("NONE\n"); 130 } 131 else 132 { 133 printf("POINT %.2lf %.2lf\n",interx(s1,s2),intery(s1,s2)); 134 } 135 } 136 } 137 printf("END OF OUTPUT\n"); 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(".\n"); 73 74 } 75 // printf("Time used = %.0lf ms\n",(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(".\n"); 128 } 129 130 return 0; 131 } View Code
转载于:https://www.cnblogs.com/Skyxj/p/3186268.html
相关资源：数据结构—成绩单生成器