5134. Пересечение двух прямых

 

Найдите точку пересечения двух прямых, заданных парой лежащих на ней точек.

 

Вход. В двух строках заданы по четыре целых числа, не превосходящих по модулю 100 – координаты точек, задающих прямые.

 

Выход. В первой строке выведите 0, если прямые не пересекаются, 1 если пересекаются ровно в одной точке и 2 если совпадают. В случае пересекающихся несовпадающих прямых во второй строке выведите координаты точки пересечения с точностью до 7 десятичных знаков.

 

Пример входа

Пример выхода

1 0 2 2

0 1 1 2

1

3 4

 

 

РЕШЕНИЕ

геометрия

 

Анализ алгоритма

Пусть заданы две точки A(x1, y1) и B(x2, y2). Прямой, проходящей через точки A и B, является геометрическое место точек X(x, y), для которых  векторы AX и AB колинеарны.

Векторы AX(x – x1, y – y1) и AB(x2 – x1, y2 – y1)  колинеарны (параллельны), если их координаты пропорциональны. Искомым уравнением прямой является условие пропорциональности координат векторов AX и AB, а именно

 =

 

Но в таком виде не представимы горизонтальные и вертикальные прямые, так как для них имеет место y1 = y2 или x1 = x2. Уравнение прямой  можно переписать в виде:

(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

 

Если уравнение прямой записать в виде ax + by = c, то

a = (y2 – y1),

b = – (x2 – x1),

c = x1y2 – y1x2

 

Построим уравнения прямых, проходящих через пары заданных точек. Далее при помощи правила Крамера находим точку пересечения прямых. Если прямые параллельны, то определяем, совпадают они или нет.

 

Реализация алгоритма

Функция kramer ищет точку пересечения прямых, заданных уравнениями a1x + b1y + c = 0 и a2x + b2y + c = 0. Функция возвращает:

· 0, если прямые пересекаются в одной точке (при этом x, y содержат координаты точки пересечения) ;

· 1, если прямые параллельны и не совпадают;

· 2, если прямые параллельны и совпадают;

 

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;

 

Прямые параллельны, если d = 0. Если dx = 0 и dy = 0, то прямые совпадают, возвращаем 2. Если прямые параллельны и не совпадают, возвращаем 1.

 

  if (d == 0) return (dx == dy && dx == 0.0) + 1;

 

Если прямые пересекаются в одной точке, то возвращаем 0, а в переменных x и y передаем ее координаты.

 

  x = dx / d; y = dy / d;

  return 0;

}

 

Основная часть программы. Читаем координаты первых двух точек. Строим уравнение прямой a1x + b1y + c = 0, проходящей через них.

 

scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

a1 = y2 - y1;

b1 = -(x2 - x1);

c1 = x1 * y2 - y1 * x2;

 

Читаем координаты следующих двух точек. Строим уравнение прямой a2x + b2y + c = 0, проходящей через них.

 

scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

a2 = y2 - y1;

b2 = -(x2 - x1);

c2 = x1 * y2 - y1 * x2;

 

Находим точку пересечения прямых (x, y) или определяем, что прямые параллельны.

 

res = kramer(a1,b1,c1,a2,b2,c2,x,y);

 

В зависимости от результата res выводим ответ.

 

if (res == 1) printf("0\n"); else

if (res == 2) printf("2\n"); else

{

  printf("1\n");

  printf("%.7lf %.7lf\n",x,y);

}