Leyni, LOLI and Line

Time Limit: 1000 MS    Memory Limit: 65536 K

Total Submit: 181(54 users)   Total Accepted: 88(52 users)       Rating:         Special Judge: No

Description

Professor Leyni likes to help LOLIs with their math.

This time, Leyni meets several LOLIs in the classroom and gets several problems about "Intersecting Lines".

The LOLIs want to know how and where two lines intersect.Leyni asks you to help him to answer.

 

Input

There are multiple test cases. The first line of input is an integer T indicating the number of test cases. Then T test cases follow.

For each test case:

Line 1. This line contains 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).

All numbers required by this problem will be in the range [-1000, 1000].

 

Output

For each test case:

Line 1.If there is no intersection, output "NONE". If they are the same line, output "LINE". Otherwise output the x and y coordinates of the point, correct to two decimal places as the sample 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 5

 

Sample Output

POINT 2.00 2.00

NONE

LINE

POINT 2.00 5.00

POINT 1.07 2.20

 

Hint

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.

 

Author

哈理工2011春季校赛

---

 

　　解析几何，斜截式的应用。

　　利用斜截式判断两条直线位置关系（共线LINE、不相交NONE、相交POINT），相交的话需要输出交点坐标。

　　思路是先分别求出两条直线斜截式的斜率k和截距b，之后就是通过比较确定两条直线的位置关系：

　　if 两条直线斜率相等　　　　if 两条直线截距也相等　　　　　　共线 LINE　　　　else 截距不相等　　　　　　平行，无交点 NONE　　else if 两条直线都垂直　　　　if 两条直线横坐标相等　　　　　　共线 LINE　　　　else 横坐标不相等　　　　　　平行，无交点 NONE　　else if 第一条直线垂直　　　　相交 POINT（交点用解析几何方法就能求出）　　else if 第二条直线垂直　　　　相交 POINT（同上）　　else 排除了斜率相等和垂直的情况，剩下的一定相交　　　　相交 POINT（联立两直线方程）

　　用斜截式解决几何问题需要注意垂直的时候是没有斜率k的，所以需要将垂直的情况拿出来单独考虑。

　　代码：

1 #include 
     
       2 int main() 3 { 4     int n; 5     scanf("%d",&n); 6     while(n--){ 7         double x1,y1,x2,y2,x3,y3,x4,y4; 8         scanf("%lf%lf%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3,&x4,&y4); 9         double k1=(y2-y1)/(x2-x1),k2=(y4-y3)/(x4-x3);10         double b1=y1-k1*x1,b2=y3-k2*x3;11         if(k1==k2){    //两条直线斜率相等12             if(b1==b2){    //两条直线截距也相等13                 printf("LINE\n");14             }15             else{    //两条直线截距不相等，说明平行，没有交点16                 printf("NONE\n");17             }18         }19         //有直线垂直的情况20         else if(x1==x2 && x3==x4){    //两条直线都垂直21             if(x1==x3)22                 printf("LINE\n");23             else 24                 printf("NONE\n");25         }26         else if(x1==x2){    //第一条直线垂直27             printf("POINT %.2lf %.2lf\n",x1,k2*x1+b2);28         }29         else if(x3==x4){    //第二条直线垂直30             printf("POINT %.2lf %.2lf\n",x3,k1*x3+b1);31         }32         else{    //一定相交33             double x = (b2-b1)/(k1-k2);34             printf("POINT %.2lf %.2lf\n",x,k1*x+b1);35         }36     }37     return 0;38 }
     

 

Freecode :