poj1269——Intersecting Lines（判断线段交点）-白红宇

poj1269——Intersecting Lines（判断线段交点）

阅读量：2343 次

发布时间：2019-05-10

本文共 3145 字，大约阅读时间需要 10 分钟。

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

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

两条线段共有三种相对位置，平行，相交和重合，题目就是给出两条线段端点坐标，然后判断这两条线段的相对位置，如果是相交还要算出交点坐标。

可以用叉积来做，将两条线段看做两条向量

平行就是这两条向量的叉积为0

重合就是他们首尾连接的向量与其中某条向量的叉积也为0

交点坐标公式可以推出，网上找了一下推理过程：

假设交点为p0(x0,y0)。则有：

(p1-p0)X(p2-p0)=0

(p3-p0)X(p2-p0)=0

展开后即是

(y1-y2)x0+(x2-x1)y0+x1y2-x2y1=0

(y3-y4)x0+(x4-x3)y0+x3y4-x4y3=0

将x0,y0作为变量求解二元一次方程组。

假设有二元一次方程组

a1x+b1y+c1=0;

a2x+b2y+c2=0

那么

x=(c1*b2-c2*b1)/(a2*b1-a1*b2);

y=(a2*c1-a1*c2)/(a1*b2-a2*b1);

因为此处两直线不会平行，所以分母不会为0。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #define INF 0x3f3f3f3f#define MAXN 5010#define Mod 10001using namespace std;struct Line{ double x1,y1,x2,y2;};Line a,b;double x,y;void inter(){ double a1=a.y1-a.y2,b1=a.x2-a.x1,c1=a.x1*a.y2-a.x2*a.y1; double a2=b.y1-b.y2,b2=b.x2-b.x1,c2=b.x1*b.y2-b.x2*b.y1; x=(c1*b2-c2*b1)/(a2*b1-a1*b2); y=(a2*c1-a1*c2)/(a1*b2-a2*b1);}int main(){ int n; printf("INTERSECTING LINES OUTPUT\n"); scanf("%d",&n); while(n--) { scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&a.x1,&a.y1,&a.x2,&a.y2,&b.x1,&b.y1,&b.x2,&b.y2); if((a.x1-a.x2)*(b.y1-b.y2)-(a.y1-a.y2)*(b.x1-b.x2)==0) //平行 { if((a.x2-a.x1)*(b.y1-a.y1)-(a.y2-a.y1)*(b.x1-a.x1)==0) //共线 printf("LINE\n"); else printf("NONE\n"); } else { inter(); printf("POINT %.2lf %.2lf\n",x,y); } } printf("END OF OUTPUT\n"); return 0;}

转载地址：http://otcvb.baihongyu.com/

你可能感兴趣的文章

已知一对夫妇有两个孩子，如果知道有一个是男孩，那么两个都是男孩的概率？