Подготовка к олимпиаде по информатике 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.

Популярные репетиторы:

Рейтинг 5 из 5: 45 отзывов
 
C самого основания своего продвижения по службе, когда еще обучался в аспирантуре, я мечтал собрать вместе 2 моих основных пристрастий: Математику, Информатику и Обучение.

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

Участвует в ведущих научных конференциях WWW, ICML и KDD . Консультации по математическим программам JupyterLab, MathCad и SPSS . Запросто программирует на JavaScript, R и Erlang. Некоторое время потрудился директором в интернет-компании по Machine Learning и TensorFlow.

Занятия проводятся по Skype и  в Москве м. Китай-город. Более 320 учащихся  поступили «на бюджет» в ВУЗы Москвы: МГУ, МАИ, ФИ и МЭИ и т.д.. Опыт учителя по математике для абитуриентов более 20 лет. Hij spreekt Nederlands.

Запись на занятия

Ваше сообщение отправлено