UVa 378 Intersecting Lines

题目描述平面上两个不同的点确定一条直线。平面上的两条直线有三种相交情况无交点平行交于一条直线重合交于一点给定四个点确定两条直线判断它们的相交情况并求出交点。输入格式第一行包含一个整数NNN1≤N≤101 \leq N \leq 101≤N≤10表示直线对的数量。接下来NNN行每行包含888个整数按顺序x1,y1,x2,y2,x3,y3,x4,y4x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4x1​,y1​,x2​,y2​,x3​,y3​,x4​,y4​表示四个点的坐标。输出格式第一行输出INTERSECTING LINES OUTPUT。对于每对直线输出一行LINE重合NONE平行POINT x y交于一点交点坐标保留两位小数最后一行输出END OF OUTPUT。样例输入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样例输出INTERSECTING LINES OUTPUT POINT 2.00 2.00 NONE LINE POINT 2.00 5.00 POINT 1.07 2.20 END OF OUTPUT题目分析问题的本质这是一个直线相交判定与交点计算问题。需要判断两条直线的位置关系并计算交点。直线表示使用直线的一般式axbyc0ax by c 0axbyc0表示直线。从两点确定直线给定两点P1(x1,y1)P_1(x_1, y_1)P1​(x1​,y1​)和P2(x2,y2)P_2(x_2, y_2)P2​(x2​,y2​)如果x1x2x_1 x_2x1​x2​垂直直线a1a 1a1b0b 0b0c−x1c -x_1c−x1​否则a−y1−y2x1−x2a -\frac{y_1 - y_2}{x_1 - x_2}a−x1​−x2​y1​−y2​​b1b 1b1c−ax1−y1c -a x_1 - y_1c−ax1​−y1​位置关系判断平行a1a2b1b2c1c2\frac{a_1}{a_2} \frac{b_1}{b_2} \frac{c_1}{c_2}a2​a1​​b2​b1​​c2​c1​​实际判断a1b2−a2b10a_1 b_2 - a_2 b_1 0a1​b2​−a2​b1​0重合平行且c1c2\frac{c_1}{c_2}c2​c1​​也成比例交点计算解方程组{a1xb1yc10a2xb2yc20 \begin{cases} a_1 x b_1 y c_1 0 \\ a_2 x b_2 y c_2 0 \end{cases}{a1​xb1​yc1​0a2​xb2​yc2​0​由克莱姆法则xb1c2−b2c1a1b2−a2b1,yc1a2−c2a1a1b2−a2b1 x \frac{b_1 c_2 - b_2 c_1}{a_1 b_2 - a_2 b_1}, \quad y \frac{c_1 a_2 - c_2 a_1}{a_1 b_2 - a_2 b_1}xa1​b2​−a2​b1​b1​c2​−b2​c1​​,ya1​b2​−a2​b1​c1​a2​−c2​a1​​参考代码// Intersecting Lines// UVa ID: 378// Verdict: Accepted// Submission Date: 2016-07-04// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleEPSILON1E-10;structpoint{doublex,y;};structline{doublea,b,c;// ax by c 0};// 两点确定直线的一般式linepointsToLine(point start,point end){line lr;if(fabs(start.x-end.x)EPSILON){lr.a1.0;lr.b0.0;lr.c-start.x;}else{lr.a-(start.y-end.y)/(start.x-end.x);lr.b1.0;lr.c-lr.a*start.x-start.y;}returnlr;}// 判断两直线是否平行boolisParallel(line line1,line line2){returnfabs(line1.a*line2.b-line2.a*line1.b)EPSILON;}// 判断两直线是否重合boolisSame(line line1,line line2){returnisParallel(line1,line2)fabs(line1.c-line2.c)EPSILON;}// 计算两直线交点pointintersect(line line1,line line2){point p;doubledetline1.a*line2.b-line2.a*line1.b;if(fabs(det)EPSILON)// 平行或重合returnp;p.x(line1.b*line2.c-line2.b*line1.c)/det;p.y(line2.a*line1.c-line1.a*line2.c)/det;returnp;}intmain(intargc,char*argv[]){intn;cinn;coutINTERSECTING LINES OUTPUTendl;doublex1,y1,x2,y2,x3,y3,x4,y4;for(inti1;in;i){cinx1y1x2y2x3y3x4y4;point p1{x1,y1},p2{x2,y2},p3{x3,y3},p4{x4,y4};line line1pointsToLine(p1,p2);line line2pointsToLine(p3,p4);if(isSame(line1,line2))coutLINEendl;elseif(isParallel(line1,line2))coutNONEendl;else{point pintersect(line1,line2);coutfixedsetprecision(2);coutPOINT p.x p.yendl;}}coutEND OF OUTPUTendl;return0;}