题目链接:
题目大意:给出四个点的坐标x1,y1,x2,y2,x3,y3,x4,y4,前两个形成一条直线,后两个坐标形成一条直线。然后问你是否平行,重叠或者相交,如果相交,求出交点坐标。
算法:二维几何直线相交+叉积
解法:先用叉积判断是否相交,如果相交的话,设交点坐标为p0(x0,y0)。向量(p0p1)和(p0p2)的叉积为0,有(x1-x0)*(y2-y0)-(y1-y0)*(x2-x0)=0;同理,求出p0和p3p4直线的式子。然后联立求解x0,y0。平行或重叠的情况就自己YY了。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define inf 0x7fffffff 8 #define exp 1e-10 9 #define PI 3.14159265410 using namespace std;11 struct Point12 {13 double x,y;14 Point(double x=0,double y=0):x(x),y() {}15 };16 typedef Point Vector;17 double cross(Vector A,Vector B)18 {19 return A.x*B.y-A.y*B.x;20 }21 Point GetLineIntersection(Point P,Vector v,Point Q,Vector w)22 {23 Point uu;24 Vector u=Point(P.x-Q.x , P.y-Q.y);25 double t=cross(w,u)/cross(v,w);26 uu.x=P.x+v.x*t;27 uu.y=P.y+v.y*t;28 return uu;29 }//调用训练指南上这个函数怎么错了,我写错了吗30 int main()31 {32 int n;33 double x1,y1,x2,y2,x3,y3,x4,y4;34 //cin>>n;35 while (cin>>n)36 {37 printf("INTERSECTING LINES OUTPUT\n");38 while (n--) {39 cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;40 Point P,Q;41 P.x=x1 ;P.y=y1 ;42 Q.x=x3 ;Q.y=y3 ;43 Vector v,w;44 v.x=x2-x1 ;v.y=y2-y1;45 w.x=x4-x3 ;w.y=y4-y3;46 if (cross(v,w)!=0)47 {48 //Vector vv=GetLineIntersection(P,v,Q,w);49 double a1,b1,c1;50 double a2,b2,c2;51 a1=y1-y2 ;b1=x2-x1 ;c1=x1*y2-y1*x2;52 a2=y3-y4 ;b2=x4-x3 ;c2=x3*y4-y3*x4;53 double x0=(b1*c2-b2*c1)/(b2*a1-b1*a2);54 double y0=(a2*c1-a1*c2)/(a1*b2-a2*b1);55 printf("POINT %.2f %.2f\n",x0,y0);56 }57 else58 {59 if (fabs(v.x)<=exp && fabs(w.x)<=exp)60 {61 if (fabs(x1-x3)<=exp)62 printf("LINE\n");63 else printf("NONE\n");64 }65 else if (fabs(v.y)<=exp && fabs(w.y)<=exp)66 {67 if (fabs(y1-y3)<=exp)68 printf("LINE\n");69 else printf("NONE\n");70 }71 else72 {73 if (fabs((y3-w.y/w.x*x3)-(y1-w.y/w.x*x1))<=exp)74 printf("LINE\n");75 else printf("NONE\n");76 }77 }78 }79 printf("END OF OUTPUT\n");80 }81 return 0;82 }