本题就是判断直线之间的关系,我的思想就是先判断是否共线,然后判断是否平行,剩下的肯定相交,直接求交点就可以了,
POJ 1269 Intersecting Lines
。在判断平行的时候只要看两者的斜率是否相等就可以了,因为在判断平行之前已经判断是否共线,所以只要斜率相等,肯定就是平行了。求交点的时候就是用的数学方法,注意斜率不存在的情况就可以了。
#include<cstdio>#include<cstring>#include#include<vector>using namespace std;struct point{ int x,y;};struct line{ point s,e;};int cross(point p1,point p2,point p3){ int x1=p2.x-p1.x,x2=p3.x-p1.x; int y1=p2.y-p1.y,y2=p3.y-p1.y; return x1*y2-x2*y1;}int isline(line l1,line l2)//是否共线{ int a=cross(l1.s,l2.s,l2.e); int b=cross(l1.e,l2.s,l2.e); if(a==0&&b==0) return 1; return 0;}int isparallel(line l1,line l2)//是否平行{ int x1=l1.s.x-l1.e.x,y1=l1.s.y-l1.e.y; int x2=l2.s.x-l2.e.x,y2=l2.s.y-l2.e.y; if(x1*y2-x2*y1==0) return 1; return 0;}void get_point(line l1,line l2)//求交点{ double x,y; if(l1.s.x==l1.e.x)//斜率不存在的情况要讨论 { double k2=(l2.s.y-l2.e.y)*1.0/(l2.s.x-l2.e.x); double b2=l2.s.y*1.0-k2*l2.s.x; y=k2*l1.s.x+b2; printf("POINT %.2lf %.2lf\n",(double)l1.s.x,y); return; } if(l2.s.x==l2.e.x) { double k1=(l1.s.y-l1.e.y)*1.0/(l1.s.x-l1.e.x); double b1=l1.s.y*1.0-k1*l1.s.x; y=k1*l2.s.x+b1; printf("POINT %.2lf %.2lf\n",(double)l2.s.x,y); return; } double k1=(l1.s.y-l1.e.y)*1.0/(l1.s.x-l1.e.x); double b1=l1.s.y*1.0-k1*l1.s.x; double k2=(l2.s.y-l2.e.y)*1.0/(l2.s.x-l2.e.x); double b2=l2.s.y*1.0-k2*l2.s.x; x=(b2-b1)/(k1-k2); y=k1*x+b1; printf("POINT %.2lf %.2lf\n",x,y);}int main(){ int n,x1,y1,x2,y2,x3,y3,x4,y4; scanf("%d",&n); printf("INTERSECTING LINES OUTPUT\n"); for(int i=1;i<=n;i++) { scanf("%d%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); line l1,l2; l1.s.x=x1,l1.s.y=y1,l1.e.x=x2,l1.e.y=y2; l2.s.x=x3,l2.s.y=y3,l2.e.x=x4,l2.e.y=y4; if(isline(l1,l2)==1) { printf("LINE\n"); continue; } if(isparallel(l1,l2)==1) { printf("NONE\n"); continue; } get_point(l1,l2); } printf("END OF OUTPUT\n"); return 0;}