[UVA][Math] 378 - Intersecting Lines
Intersecting Lines
| 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;
}