Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат

[isst]

Прошу помочь мне с решением задачи:

Многоугольник на плоскости задан целочисленными координатами своих N вершин в декартовой системе координат. Требуется найти количество точек с целочисленными координатами, лежащих на границе многоугольника. Стороны многоугольника друг с другом не соприкасаются (за исключением соседних - в вершинах) и не пересекаются.
Ограничения: 3 <= N <= 100 000, координаты вершин целые и по модулю не превосходят 1 000 000 000.

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

Выходные данные
Вывести одно число - количество точек с целочисленными координатами на границе многоугольника.

Вот мой код, если интересно. Однако он выдает иногда неправильные ответы, а также иногда время работы программы превышает максимальное (для нее дано максимальное 1 секунда, а у меня в одном тесте 1.064 сек). Тестировалась на informatics.mccme.ru, задача номер 668:

function NOD(a, b:Longint):Longint;
begin
while (a>0) and (b>0) do
begin
if (a>b) then a:=a-b
else b:=b-a;
end;
NOD:=a+b
end;
var n,i,count:Longint;
X, Y:array[1..100000] of Longint;
begin
readln(n);
for i := 1 to n do read(X[i],Y[i]);
count:=0;
for i := 1 to n-1 do
begin
if (X[i]=X[i+1]) or (Y[i]=Y[i+1]) then count:=count+abs(X[i]-X[i+1])+abs(Y[i]-Y[i+1])
else count:=count+NOD(abs(X[i]-X[i+1]),abs(Y[i]-Y[i+1]));
end;
if (X[1]=X[n]) or (Y[1]=Y[n]) then count:=count+abs(X[1]-X[n])+abs(Y[1]-Y[n])
else 
count:=count+NOD(abs(X[1]-X[n]),abs(Y[1]-Y[n]));
writeln(count)
end.

[Аватар]

Ошибка скорее всего из-за count: Longint. Сделай int64. Для быстродействия вместо алгоритма Евклида можно бинарный попробовать, возможно быстрей будет

[Poma][a]

А что такое бинарный?

И да.. Я за Евклида с делением.. Вот
А еще массив нафиг не нужен

[Аватар]

https://ru.wikipedia.org/wiki/%D0%91...9D%D0%9E%D0%94

Это и есть с делением видимо

[Poma][a]

Сообщение от Аватар

https://ru.wikipedia.org/wiki/%D0%91...9D%D0%9E%D0%94

Это и есть с делением видимо

Вау, забавно.
Не знал. Спасибо!
Я имел ввиду вычисление НОД через НОК (который вычисляется mod'ом)

[isst]

Сообщение от Аватар

Ошибка скорее всего из-за count: Longint. Сделай int64. Для быстродействия вместо алгоритма Евклида можно бинарный попробовать, возможно быстрей будет

Спасибо, ща попробую.

Насчет Int64, Спасибо Огромное, тот тест, который выдавал неправильный ответ, прокатил. Я, честно говоря, подумывал над этим, но остановился на LongInt и до Int64 не допер)))

Все, ребят, всем огромное спасибо, все тесты прошли!!! В итоге обошелся без бинарного алгоритма Евклида, массивы оставил, LongInt --> Int64. Вот код рабочей программы, если кому интересно и/или надо:

function nod(a,b:int64):int64;
var c:int64;
begin
while b<>0 do
begin
c:=a mod b;
a:=b;
b:=c;
end;
nod:=a
end;
var count:int64;
x,y:array[1..100000] of int64;
n,i:longint;
begin
readln(n);
for i := 1 to n do read(x[i],y[i]);
count:=0;
for i: = 1 to n-1 do
begin
if (x[i]=x[i+1]) or (y[i]=y[i+1])
then count:=count+abs(x[i]-x[i+1])+abs(y[i]-y[i+1])
else count:=count+nod(abs(x[i]-x[i+1]),abs(y[i]-y[i+1]));
end;
if (x[1]=x[n]) or (y[1]=y[n])
then count:=count+abs(x[1]-x[n])+abs(y[1]-y[n])
else count:=count+NOD(abs(x[1]-x[n]),abs(y[1]-y[n]));
writeln(count)
end.

[Аватар]

А такой вариант, что эффективней?

function NOD(a,b: Longint): Longint;
begin
  if (a=0) or (a=b)                     then NOD:=b
  else if b=0                           then NOD:=a
  else if (a=1) or (b=1)                then NOD:=1
  else if (a and $1=0) and (b and $1=0) then NOD:=2*NOD(a div 2,b div 2)
  else if a and $1=0                    then NOD:=NOD(a div 2,b)
  else if b and $1=0                    then NOD:=NOD(a,b div 2)
  else if a>b                           then NOD:=NOD((a-b) div 2,b)
                                        else NOD:=NOD(a,(b-a) div 2);
end;

var n,i,x0,y0,x1,y1,x2,y2: Longint;
    count: Int64;

begin
  readln(n);
  read(x0,y0);
  x1:=x0; y1:=y0;
  count:=0;
  for i:=2 to n do begin
    read(x2,y2);
    count:=count+NOD(Abs(x2-x1),Abs(y2-y1));
    x1:=x2; y1:=y2;
  end;
  count:=count+NOD(Abs(x1-x0),Abs(y1-y0));
  writeln(count)
end.

[isst]

Сообщение от Аватар

А такой вариант, что эффективней?

Проверил и понял, что гораздо эффективнее Ваш вариант. И работает быстрее, и памяти жрет меньше. Понимаю, что без массивов проще, и что если даже использовать их, нужно было динамический делать.
В любом случае спасибо!

Сообщение от isst

Проверил и понял, что гораздо эффективнее Ваш вариант. И работает быстрее, и памяти жрет меньше. Понимаю, что без массивов проще, и что если даже использовать их, нужно было динамический делать.
В любом случае спасибо!

Аватар, я решил чисто ради интереса скрестить наши программы: я оставил свою функцию НОДа, убрал массивы и тело программы взял Ваше. Вот что у меня получилось:

function NOD(a, b:Int64):Int64;

var c:Int64;

begin
  while (b <> 0) do
  begin
    c:= a mod b;
    a:= b;
    b:= c;
  end;
  NOD:= a;
end;

var count:Int64;
    n, i, x, y, x1, y1, x2, y2:LongInt;
    
begin
  readln(n);
  read(x, y);
  x1:= x; 
  y1:= y;
  count:= 0;
  for i:= 2 to n do 
  begin
    read(x2, y2);
    count:= count + NOD(abs(x2 - x1), abs(y2 - y1));
    x1:= x2;
    y1:= y2;
  end;
  count:= count + NOD(abs(x1 - x), abs(y1 - y));
  writeln(count);
end.

В итоге тесты показали, что среднее время работы (на 7 тестах) оказалось абсолютно одинаковым, да и разброс в каждом из тестов был небольшой +- 0.001 сек. Можно ли отсюда сделать вывод, что бинарный алгоритм Евклида и тот алгоритм, который предложил я в конечном варианте своей программы:

function NOD(a, b:Int64):Int64;
 
var c:Int64;
 
begin
  while (b <> 0) do
  begin
    c:= a mod b;
    a:= b;
    b:= c;
  end;
  NOD:= a;
end;

- можно ли сделать вывод, что они практически идентичны по быстродействию?

Сообщение от isst

Проверил и понял, что гораздо эффективнее Ваш вариант. И работает быстрее, и памяти жрет меньше. Понимаю, что без массивов проще, и что если даже использовать их, нужно было динамический делать.
В любом случае спасибо!

Аватар, я решил ради интереса скрестить наши коды: я оставил свою функцию НОДа и взял Ваше тело программы. В итоге получилось, что среднее время работы на 7 тестах оказалось абсолютно одинаковым! Да и отклонение во времени в каждом тесте было +- 0.001 секунды. Можно ли из этого сделать вывод, что бинарный алгоритм Евклида эквивалентен по быстродействию моей функции НОДа?

[Аватар]

можно ли сделать вывод, что они практически идентичны по быстродействию?

Не стал бы так однозначно утверждать. Много зависит от тестовых данных, может из наших форумских теоретиков кто-то оценит сложность алгоритма, к своему стыду не умею

[isst]

Сообщение от Аватар

Не стал бы так однозначно утверждать. Много зависит от тестовых данных, может из наших форумских теоретиков кто-то оценит сложность алгоритма, к своему стыду не умею

Спасибо в любом случае!