5134. Intersection of two lines
Find the intersection point of two lines. Each line is given with the
pair of points on it.
Input. Two lines are given. Each line contains four integers, not greater than
100 by absolute value – the coordinates of the points specifying the lines.
Output. Print in the first line 0 if lines do not intersect,
print 1 if lines intersect in one point and print 2 if lines
coincide. If the lines intersect each other and do not coincide, print in the
second line the coordinates of intersection point with 7 digits after the
decimal point.
|
Sample input |
Sample output |
|
1 0 2 2 0 1 1 2 |
1 3 4 |
SOLUTION
geometry
Algorithm analysis
Let two points A(x1, y1) and B(x2, y2) be given. The
line passing through the points A and B is the locus of points X(x, y) for
which the vectors AX and AB are collinear.
Vectors AX(x – x1, y – y1)
and
AB(x2 – x1, y2 – y1) are collinear (parallel), if their coordinates are
proportional. The desired equation of the straight line is the condition of
proportionality of coordinates of the vectors AX and AB:
= 
But horizontal and vertical lines
cannot be represented in this form, since y1 = y2
or x1 = x2 takes place for them. The equation of
a straight line can be rewritten as:
(x
– x1) (y2 – y1) = (x2
– x1) (y – y1),
x (y2 – y1) – x1
(y2 – y1) = (x2
– x1) y – (x2 – x1) y1,
(y2
– y1) x – (x2 – x1) y – x1y2 + y1x2
= 0,
(y2
– y1) x – (x2 – x1) y = x1y2 – y1x2
If the equation of a straight line is
written as ax + by = c, then
a = (y2
– y1),
b = – (x2 – x1),
c = x1y2 – y1x2
Construct the equations
of lines passing through the pairs of
given points. Then using
Cramer’s rule find the
intersection point of the lines. If the lines are parallel, then determine
whether they coincide or not.
Algorithm realization
Function kramer finds the intersection point of the lines given by equations a1x + b1y + c
= 0 and a2x + b2y + c = 0. Function returns:
· 0, if the lines intersect at one
point (x, y contain the coordinates of the intersection point);
· 1, if the lines are
parallel and do not coincide;
· 2, if the lines are
parallel and coincide;
int kramer(double
a1, double b1, double
c1,
double a2, double b2,
double c2,
double &x, double &y)
{
double d = a1 * b2 - a2 * b1;
double dx = c1 * b2 - c2 * b1;
double dy = a1 * c2 - a2 * c1;
The lines are parallel, if d = 0. If dx = 0 and dy = 0, the lines
coinside, return 2. If lines are parallel and do not coinside, return 1.
if (d == 0) return
(dx == dy && dx == 0.0) + 1;
If the lines intersect at one point, then return 0, and
in the variables x and y pass its coordinates.
x = dx / d; y = dy /
d;
return 0;
}
The main part of the program. Read the coordinates of the first two points. Construct the equation of the line a1x + b1y + c
= 0 that pass through them.
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
a1 = y2 - y1;
b1 = -(x2 - x1);
c1
= x1 * y2 - y1 * x2;
Read the
coordinates of the next two points. Construct
the equation of the line a2x + b2y + c = 0 that pass through them.
scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);
a2 = y2 - y1;
b2 = -(x2 - x1);
c2 = x1 * y2 - y1
* x2;
Find the intersection point of
the lines (x, y) or determine that
the lines are parallel.
res = kramer(a1,b1,c1,a2,b2,c2,x,y);
Depending on the value of res, print the
answer.
if (res == 1) printf("0\n");
else
if (res == 2) printf("2\n");
else
{
printf("1\n");
printf("%.7lf %.7lf\n",x,y);
}