006. Точки отрезка

(Время - 1 сек., память - 16 Мб)

Концы отрезка на плоскости имеют целочисленные координаты.

Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат этому отрезку.

Входные данные

В единственной строке входного файла input.txt записаны четыре числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 109.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести одно число – количество точек на заданном отрезке, имеющих целочисленные координаты.

Примеры

input.txt

output.txt

1

1 1 2 2

2

2

0 0 -2 -2

3

3

1 1 1 10

10

Разбор

Пусть (x1, y1), (x2, y2) – координаты концов отрезка. Переместим отрезок и, если нужно, отразим его относительно вертикали и горизонтали так, чтобы его левый нижний конец находился в точке (0, 0), а второй имел координаты (x, y)=(|x1-x2|, |y1-y2|). Очевидно, что количество «целочисленных» точек на отрезке при этих перемещениях не изменяется. Найдем наибольший общий делитель координат отрезка, d=НОД(x, y). Тогда x=k∙d, y=l∙d, то точки (k, l), (2k, 2l), …,((d-1)∙k, (d-1)∙l) принадлежат отрезку, поэтому всего «целочисленных» точек (d‑1)+2=d+1.

Программа на Паскале

{Автор программы - А.В.Алексеев,  дата написания - 23.04.2012}

var

  x1, y1, x2, y2, a, b, c : longint;

begin

  assign(input,'input.txt'); reset(input);

  assign(output,'output.txt'); rewrite(output);

  read(x1,y1,x2,y2);

  a:=abs(x1-x2); b:=abs(y1-y2);

  if a=0 then write(b+1) else

    if b=0 then write(a+1) else

    begin

      while b>0 do

      begin c:=a mod b; a:=b; b:=c end;

      write(a+1)

    end

end.

Программа на С

 

Информация о задаче

Автор, источник

 

Олимпиада

Муниципальный этап олимпиады в Ханты-Мансийском АО-Югре, 2007-2008 уч. год, 2-й тур

Тематика

Геометрия

Примерная сложность

42%

Ссылки в Интернете

Условие , сдача решения – http://acmu.ru/index.asp?main=task&id_task=319

Наш сайт

Сдача решения –

Тесты – Rar

Задача подготовлена

Автор, дата –  Алексеев А.В., 26.04.2012