Intersecting Lines

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 . Thus each of these input lines represents two lines on the plane: the line through and and the line through and . The point is always distinct from . Likewise with and .

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

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

INTERSECTING LINES OUTPUT
POINT 2.00 2.00
NONE
LINE
POINT 2.00 5.00
POINT 1.07 2.20
END OF OUTPUT

---

公式

#include <stdio.h>
struct Point {
    int x, y;
};
struct Segment {
    Point s, e;
};
void solve(Segment a, Segment b) {
    int a1, b1, c1, a2, b2, c2;
    int D, Dx, Dy;
    a1 = a.s.y-a.e.y, b1 = -a.s.x+a.e.x;
    a2 = b.s.y-b.e.y, b2 = -b.s.x+b.e.x;
    c1 = a1*a.s.x + b1*a.s.y;
    c2 = a2*b.s.x + b2*b.s.y;
    D = a1*b2-a2*b1;
    Dx = c1*b2 - c2*b1;
    Dy = a1*c2 - a2*c1;
    if(!D && (Dx || Dy))
        puts("NONE");
    else if(!D && !Dx && !Dy)
        puts("LINE");
    else
        printf("POINT %.2lf %.2lf\n", (double)Dx/D, (double)Dy/D);
}
int main() {
    int t;
    scanf("%d", &t);
    puts("INTERSECTING LINES OUTPUT");
    while(t--) {
        Segment a, b;
        scanf("%d %d %d %d", &a.s.x, &a.s.y, &a.e.x, &a.e.y);
        scanf("%d %d %d %d", &b.s.x, &b.s.y, &b.e.x, &b.e.y);
        solve(a, b);
    }
    puts("END OF OUTPUT");
    return 0;
}