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

Задача «Зарница»

2 секунды и 64 Мб памяти

В ходе военно-патриотической игры "Зарница" школьник Петя получил задание от командира перенести отрядное знамя из одного окопа в другой. Из донесений разведки стало известно, что Пете может помешать прямолинейный забор.

(Если забор мешает движению, его можно обойти, можно также двигаться вдоль забора.) Помогите Пете определить длину кратчайшего пути между окопами, пренебрегая размерами окопов и толщиной забора.

Формат входного файла input.txt

В первой строке записаны четыре целых числа х1, у1 и х2, у2 - координаты первого и второго окопов, во второй строке записаны четыре целых числа х3, у3 и х4, у4 - координаты концов забора (его длина не равна нулю).

Окопы и забор не имеют общих точек. Все числа записаны через пробел и находятся в диапазоне [-1000; 1000].

Формат выходного файла output.txt

Выходной файл содержит единственное число -длину кратчайшего пути между окопами, округлённую до трёх цифр в дробной части.

var
  x1,y1,x2,y2,x3,y3,x4,y4,d1,d2:real;

begin
  assign(input, 'input.txt');reset(input);
  assign(output, 'output.txt');rewrite(output);
  read(x1,y1,x2,y2,x3,y3,x4,y4);
  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
  write(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)):0:5) else
  begin
     d1:=sqrt((x1-x3)*(x1-x3)+(y1-y3)*(y1-y3))+sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)) ;
  d2:=sqrt((x1-x4)*(x1-x4)+(y1-y4)*(y1-y4))+sqrt((x4-x2)*(x4-x2)+(y4-y2)*(y4-y2));
      if d1<d2 then    write(d1:0:5) else   write(d2:0:5);
  end;
  close(input);
  close(output);
end.





close
 

Разбор задачи №3 "Зарница"

В третьей задаче сначала нужно выяснить пересекаются ли отрезки 1-2 и 3-4. Это можно сделать, определив, как расположены каждая из пар точек относительно прямой проходящей через 2 другие точки.

Если точки 1 и 2 находятся в разных полуплоскостях относительно прямой, проходящей через точки 3 и 4 и если точки 3 и 4 находятся в разных полуплоскостях относительно прямой, проходящей через точки 1 и 2, то отрезки 1-2 и 3-4 пересекаются во внутренней точке каждого из отрезков.

В этом случае следует выбрать меньшую из длин ломанных 1-3-2 или 1- 4-2 , в противном - длину отрезка 1-2. Координаты точек, расположенных в одной полуплоскости относительно прямой, при подстановке этих координат в уравнение этой прямой ах+ву+с=0 дают значения одного знака, а из противоположных - разных знаков.

Используя это свойство нетрудно проверить, пересекаются ли отрезки.