Тема 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;

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

function kol(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;

if z1>y1 then

min:=z1;

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

max:=y2;

if z2<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;

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

Begin

while sqr(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).

Input.txt	Output.txt
7 1 4 9 3 3 8 4 2 1 8 1 6 7 7 2 7 4 4 5 4 5 2 6 5	(1,1) (2,1) (2,2) (2,3) (3,3) (3,4) (3,5) (4,5) (5,5)

 

Const

File_Dat='Input.txt';{константа хранит имя входного файла}

File_Sol='Output.txt';{константа хранит имя выходного файла}

Var

X: array [1..30,1..30] of Longint;{массив для хранения количества монет в комнатах}

Y: array [0..30,0..30] of longint;{массив для хранения сумм монет при переходе}

n,i,j: byte;

Begin

assign(Input, File_Dat);{связываем файловую переменную и входной файл}

reset(Input);{открываем файл для чтения}

readln(N);{считываем количество комнат на этаже}

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

for i:=1 to N do

for j:=1 to N do

read(X[i,j]);

close(Input);{закрываем входной файл}

{заполняем массив сумм нулями}

for i:=0 to n do

for j:=0 to n do

Y[i,j]:=0;

{Заполняем массив сумм}

for i:=1 to N do

for j:=1 to N do

if Y[i-1,j]>Y[i,j-1] then {Определяем комнату с наибольшим количеством монет}

Y[i,j]:=X[i,j]+Y[i-1,j]{записываем в массив сумм сумму монет текущей и соседней комнаты снизу}

Else

Y[i,j]:=X[i,j]+Y[i,j-1];{записываем в массив сумм сумму монет текущей и соседней комнаты справа}

assign(Output,File_Sol);{связываем выходной файл и файловую переменную}

rewrite(Output);{открываем файл для записи}

writeln(Y[n,n]);{выводим максимальное количество монет}

write('(',n,',',n,')'); {вывод координат последней комнаты}

{вывод пути, обратный обход массива сумм}

i:=n;

j:=n;

s:='';

{Обход массива сумм в обратную сторону}

while (i>0) and (j>0) do

Begin

if (Y[i,j]-X[i,j])=Y[i-1,j] then i:=i-1

else j:=j-1;

if (i<>0) and (j<>0) then

write(Output,'(',i,',',j,')');

end;

close(Output);

end.