Подготовка к олимпиаде по информатике 10-11 класс. Задача 10. Ортогональную целочисленную решетку, состоящую из точек с целыми координатами в декартовой системе координат, будем обозначать через Z2. На решетке Z2 дан простой многоугольник (т. е.
Подготовка к олимпиаде по информатике 10-11 класс
Задача 10 (16 баллов). Ортогональную целочисленную решетку, состоящую из точек с целыми координатами в декартовой системе координат, будем обозначать через Z2. На решетке Z2 дан простой многоугольник (т. е. без самокасаний и самопересечений, но не обязательно выпуклый) с вершинами в узлах решетки Z2. Найти количество точек решетки Z2, лежащих на границе многоугольника. Входные данные. Входной файл содержит целое число N (3 ≤ N ≤ 1000) – количество вершин многоугольника и последовательность из N пар целочисленных координат вершин многоугольника. Все координаты по модулю не больше 106. Вершины многоугольника заданы в порядке их обхода против часовой стрелки. Выходные данные. В выходной файл вывести одно целое число – количество точек решетки Z2, лежащих на границе многоугольника.
Подготовка к олимпиаде по информатике 10-11 класс
Решение задачи 10.Язык Паскаль.
program Project_1_10;
{$APPTYPE CONSOLE}
uses SysUtils;
type node = record x, y: integer; end;
var f, g: textfile;
N, a, b, local_npoint, global_npoint, i: integer;
prev, next, start: node;
// Наибольший общий делитель (рекурсивная функция)
function gcd(a, b: integer): integer;
begin
if (b = 0) then result := a
else result := gcd(b, a mod b);
end;
begin
assignfile(f, 'input.txt');
assignfile(g, 'output.txt');
try
reset(f);
rewrite(g);
try
global_npoint := 0;
read(f, N);
read(f, next.x, next.y);
start.x := next.x;
start.y := next.y;
for i := 2 to N do
begin
prev.x := next.x;
prev.y := next.y;
read(f, next.x, next.y);
a := abs(next.x - prev.x);
b := abs(next.y - prev.y);
if (a = 0) then local_npoint := b + 1
else if (b = 0) then local_npoint := a + 1
else local_npoint := gcd(a, b) + 1;
inc(global_npoint, local_npoint);
end;
prev.x := next.x;
prev.y := next.y;
next.x := start.x;
next.y := start.y;
if (a = 0 ) then local_npoint := b + 1
else if (b = 0) then local_npoint := a + 1
else local_npoint := gcd(a, b) + 1;
inc(global_npoint, local_npoint);
writeln(g, global_npoint - N);
finally
closefile(f);
closefile(g);
end;
except
on EInOutError do Writeln('EInOutError!');
end;
end.
