Тема 3: Аналитическая геометрия

«Газон»

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

Входные данные: lawn.in. В первой строке входного файла содержатся четыре целых числа x1, y1, x2, y2 (−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000).

Во второй строке входного файла содержатся три целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)

Выходные данные: lawn.out. В выходной файл необходимо вывести одно целое число — число пучков травы, которые были и пострижены, и политы.

Пример входных и выходных данных

lawn.in	lawn.out
0 0 5 4 4 0 3

{Одно из возможных решений данной задачи заключается в следующем. Для каждой прямой, содержащей все пучки травы с равной координатой по оси абсцисс (аналогично можно рассматривать и ось ординат), найдем ее точки пересечения с окружностью, отображающей область действия поливальной установки, если, конечно, такие точки существуют. Получив данные точки, не сложно посчитать количество пучков травы на данной прямой одновременно и политых, и постриженных. Далее, просуммировав найденные числа для всех прямых, можно найти ответ на поставленную задачу.}

Var

x1,y1,x2,y2,x3,y3,x: longint;

k,r,y : longint;

input,output: text;

{функция определяет количество пучков травы, которые политы и подстрижены в исследуемом ряду}

functionkol(x,z1,z2:longint):longint;

Var

min,max,k: longint;

Begin

if(x<x1)or(x>x2)or(z1>y2)or(z2<y1) then{ряд не пересекает подстриженную область}

k:=0 {количество политых и подстриженных пучков равно 0}

else{иначе}

Begin

{определяем минимальную координату Y пучка травы, который полит}

min:=y1;

ifz1>y1 then

min:=z1;

{определяем максимальную координату Y пучка травы, который полит}

max:=y2;

ifz2<y2 then

max:=z2;

k:=max-min+1 {считаем количество политых пучков травы в, принадлежащих подстриженной области}

end;

kol:=k

end;

Begin

{связываем файловые переменные и файлы, открываем для чтения и записи}

assign(input, 'lawn.in');

reset(input);

assign(output, 'lawn.out');

rewrite(output);

{считываем координаты вершин прямоугольной области}

readln(input,x1,y1,x2,y2);

{считываем координаты центра области полива и радиус полива}

read(input,x3,y3,r);

k:=kol(x3,y3-r,y3+r); {определяем, количество подстриженных и политых пучков травы в вертикальном ряду, проходящем через центр площади полива}

y:=r;

forx:=1 tor-1 do{пересчет всех вертикальных рядов, которые вмещаются на территорию от края до центра площади полива (не включая центральный ряд)}

Begin

whilesqr(x)+sqr(y)>sqr(r) do{определяется граничная точка y, принадлежащая площади полива}

y:=y-1;

k:=k+kol(x3+x,y3-y,y3+y)+kol(x3-x,y3-y,y3+y);{считается количество постриженых и политых пучков травы в рядах влево и вправо от центра полива}

end;

k:=k+kol(x3+r,y3,y3)+kol(x3-r,y3,y3);{считается количество постриженных и политых пучков травы в рядах, который проходят по касательной к площади полива}

write(output,k); {запись результата в файл}

close(input);

close(output);

end.

Тема 4: Перебор вариантов

«Буратино в замке»

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

Входные данные: Input.txt. В первой строке файла находится одно число N (1≤N≤30). В каждой i-ой из следующих N строк находится N чисел, которые обозначают количество монет в комнате (i,j).

Выходные данные: Output.txt. в первую строку файла выводится одно целое число – количество монет, которые удалось собрать Буратино. Во второй строке – маршрут – номера комнат, в которых побывал Буратино, начиная с комнаты (N,N) и заканчивая комнатой (1,1).