Олимпиадная информатика - 2010

Задача «Два отрезка»

Два отрезка АВ и CD на плоскости заданы координатами своих концов - точек А, В, С и D. Требуется найти пересечение этих отрезков и вывести: слово Empty, если эти отрезки не пересекаются; координаты точки пересечения, если пересечение состоит из единственной точки; координаты точек - концов отрезка пересечения, если пересечение заданных отрезков является отрезком. Входные данные

Входной файл содержит координаты точек А, В, С и D - целые числа, не превосходящие 1 ООО по абсолютной величине. Отрезки могут быть вырожденными. Выходные данные

Выходной файл должен содержать ответ на задачу в указанном формате. Числа следует выводить не менее чем с 6 знаками после точки.

INPUT.TXT

00 99 95 05

OUTPUT.TXT

5.000000 5.000000

program aa;
 var x1,y1,x2,y2,x3,y3,x4,y4,d,dx,dy,a1,a2,c1,c2,b1,b2:real;
   {q,w:char;f:boolean;                    }
   label 1;
function odpr(x1,y1,x2,y2,x3,y3,x4,y4:real):boolean;
begin
 if ((x3-x1)*(y2-y1)-(y3-y1)*(x2-x1)=0)and((x4-x1)*(y2-y1)-(y4-y1)*(x2-x1)=0)
 then odpr:=true else odpr:=false;
end;
function per(x1,y1,x2,y2,x3,y3,x4,y4:real):boolean;
begin
 if (((x3-x1)*(y2-y1)-(y3-y1)*(x2-x1))*((x4-x1)*(y2-y1)-(y4-y1)*(x2-x1))<±0)and
 (((x1-x4)*(y3-y4)-(y1-y4)*(x3-x4))*((x2-x4)*(y3-y4)-(y2-y4)*(x3-x4))<±0)
 then per:=true else per:=false;
end;
begin
 assign(input,'input.txt');reset(input);
 assign(output,'output.txt');rewrite(output);
  read(x1,y1,x2,y2,x3,y3,x4,y4);
  if odpr(x1,y1,x2,y2,x3,y3,x4,y4)
  then begin
    if x2<x1 then begin d:=x1;x1:=x2;x2:=d;d:=y1;y1:=y2;y2:=d;end;
    if x4<x3 then begin d:=x3;x3:=x4;x4:=d;d:=y3;y3:=y4;y4:=d;end;
    if x3<x1 then begin d:=x1;x1:=x3;x3:=d;d:=y1;y1:=y3;y3:=d;
     d:=x2;x2:=x4;x4:=d;d:=y2;y2:=y4;y4:=d;end;
    if x1=x2 then begin if  y1>y2 then begin d:=y1;y1:=y2;y2:=d;end;end;
    if x3=x4 then begin if  y3>y4 then begin d:=y3;y3:=y4;y4:=d;end;end;
    if (x1=x3)and(y1>y3) then
    begin d:=x1;x1:=x3;x3:=d;d:=y1;y1:=y3;y3:=d;
     d:=x2;x2:=x4;x4:=d;d:=y2;y2:=y4;y4:=d;end;
    if (x1=x3)and(y1=y3) then
    begin
      write(x1:0:6,' ',y1:0:6);
      if (y2-y1)*(y4-y3)>0 then begin
      if abs(y2-y1)<abs(y4-y3) then write(' ',x2:0:6,' ',y2:0:6)
      else  write(' ',x4/1:0:6,' ',y4/1:0:6)
      end;
    end else
    begin
      if (x2=x3)and(y2=y3) then  write(x2:0:6,' ',y2:0:6)
      else if (x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)> (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)
       then write('Empty') else
        begin
         write(' ',x3:0:6,' ',y3:0:6);
         if not((x3=x4)and(y3=y4)) then
         if (x4-x3)*(x4-x3)+(y4-y3)*(y4-y3)> (x2-x3)*(x2-x3)+(y2-y3)*(y2-y3)
       then  write(' ',x2:0:6,' ',y2:0:6)
       else write(' ',x4:0:6,' ',y4:0:6)
       end;
    end;
   end
  else if per(x1,y1,x2,y2,x3,y3,x4,y4) then
  begin
   a1:=y2-y1;b1:=x1-x2;c1:=x1*(y2-y1)-y1*(x2-x1);
   a2:=y4-y3;b2:=x3-x4;c2:=x3*(y4-y3)-y3*(x4-x3);
   d:=a1*b2-b1*a2;dy:=a1*c2-c1*a2;dx:=c1*b2-b1*c2;
   write(dx/d:0:6,' ',dy/d:0:6);
  end else write('Empty');
 close(input);close(output);
 end.







close
 

Разбор задачи №2 "Два отрезка"

Решение распадается на 2 принципиально различных случая:

1.Все 4 точки лежат на одной прямой

2.Точки не лежат на одной прямой. В первом случае надо аккуратно рассмотреть все возможные случаи. Для упрощения работы концы отрезков надо отсортировать так, чтобы первая точка была левее(x1<x2), если отрезок параллелен оси ОУ (х1=х2) то, чтобы первая точка была ниже (у1<у2). После этого надо отсортировать отрезки так чтобы первый был левее(x1<x3), если х1=х3 ,то чтобы первый был ниже(y1<y3). В результате число возможных вариантов значительно уменьшается. А)второй отрезок начинается после первого (х2<x3)– общих точек нет. Б)Второй отрезок начинается в концу первого (х2=х3 и у2=у) ответ одна точка Т3 В)второй отрезок начинается внутри первого(х3<x2 или х3=х3 и у3< 2): В1) один из отрезков вырожденный – ответ одна точка Т3, В2) второй отрезок заканчивается внутри первого – ответ отрезок Т3-Т4 В3)конец второго отрезка вне первого отрезка – ответ отрезок Т3-Т2

Если точки на лежат на одной прямой, то сортировка не обязательна, пересечение находим таким образом: Прямая разбивает плоскость на 2 полуплоскости. Если концы отрезка лежат в разных полуплоскостях, то отрезок пересевает прямую, если в одной – не пересекает. 2 отрезка пересекаются если каждый из них пересекает прямую, на которой лежит другой отрезок. Проверить это можно таким образом: если подставить в уравнение прямой координаты точек одной полуплоскости, то получим значения одного знака (на пример положительные).

Координаты точек другой полуплоскости дадут значения другого знака ( в примере - отрицательного). При умножении 2 чисел одного знака имеем положительный результат, разного знака – отрицательный.

Запишем уравнение прямой, проходящей через первую и вторую точки , (x-x1)(y2-y1)-(y-y1)(y2-y1)=0, подставим в его левую координаты третьей и четвёртой и перемножим полученные результаты.

Затем то же проделаем для прямой, проходящей через третью и четвертую точки и точек один и два.

Её координаты найдем, решив соответствующую систему полученных уравнений. Легче сделать это методом Крамера. Прилагаю вариант листинга, в нём все переменные типа REAL.

Можно использовать и целый тип INT64. При использовании типа LONGINT данный вариант программы даёт неверный результат в 2 тестах (№14 и №36), т.к. при умножении получаем выход за допустимый интервал значений.