Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
for i:=1 to neb_num do with arr_neb[i] do
if (x=x1)and(y1<=y)and(y<=y2)then begin Wave:=false; Exit end
end
else
if y1=y2 then
begin
if x1>x2 then
begin
t:=x1; x1:=x2; x2:=t
end;
for i:=1 to neb_num do with arr_neb[i] do
if (y=y1)and(x1<=x)and(x<=x2)then begin Wave:=false; Exit end
end
else
begin
k:=(y2-y1)/(x2-x1);
for i:=1 to neb_num do with arr_neb[i] do
begin
k:=(y2-y1)/(x2-x1);
p1:=k*(x-0.5-x1)+y1;
{можно задеть угол}
if (y-half<p1)and(p1<y+half)then begin Wave:=false; Exit end;
p2:=k*(x+0.5-x1)+y1;
if (y-half<p2)and(p2<y+half)then begin Wave:=false; Exit end;
if (abs(y-0.5-p1)<eps)and(abs(y+0.5-p2)<eps)or
(abs(y+0.5-p1)<eps)and(abs(y-0.5-p2)<eps)
then begin Wave:=false; Exit end;{проходит через углы
небоскрёба}
k:=(x2-x1)/(y2-y1);
p1:=k*(y-0.5-y1)+x1;
if (x-half<p1)and(p1<x+half)then begin Wave:=false; Exit end;
p2:=k*(y+0.5-y1)+x1;
if (x-half<p2)and(p2<x+half)then begin Wave:=false; Exit end
end
end;
end;
function Cover(var map:TSet;new_a:integer):boolean;
{покрыть карту map проходящим сигналом из антенны new_a}
var x,y,a:integer;
begin
Cover:=true;
for x:=1 to n do
for y:=1 to m do
begin
a:=GetIndex(x,y);
if not(a in map) and not(a in neb) then
if Wave(new_a,a) then map:=map+[a] else Cover:=false
end
end;
procedure Think;{расстановка антенн}
var
vspom:TSet;{рабочее расположение}
num:integer;{рабочее число антенн}
procedure Step(map:TSet;new_a:integer);
{поставить антенну new_a на карту map}
var x,y:integer;
begin
if not Cover(map,new_a) then
for x:=1 to n do
for y:=1 to m do
begin
new_a:=GetIndex(x,y);
if not(new_a in map)and not(new_a in neb) then
begin
vspom:=vspom+[new_a]; inc(num);
Step(map,new_a);
vspom:=vspom-[new_a]; dec(num)
end
end
else
if num<ant_num then
begin
ant_num:=num;
ant:=vspom
end
end;
var
x,y,a:integer;
begin
ant:=[]; ant_num:=Lmax+1;
for x:=1 to n do{ставим в качестве 1-ой различные антенны }
for y:=1 to m do
begin
a:=GetIndex(x,y);
if not(a in neb) then
begin
vspom:=[a]; num:=1;
Step([],a)
end
end
end;
begin
Load;
Think;
Save
end.
Работа выполнена в рамках Федеральной целевой программы
«Интеграция» по направлению «Воссоздание студенческих
научных школ и олимпиад» (проект Р 0054).
Издается при финансовой поддержке ООО ПФ «Джуди».
Авторы :
доц. О .Ф.Ускова,
доц. О .Д .Горбенко ,
проф. А.И .Шашкин
Олимпиадные задачи по программированию. Лучшие
решения. Часть 1.: Учебное издание/ О .Ф.Ускова, О .Д .Горбенко ,
А.И .Шашкин – Воронеж: ООО ПФ «Джуди», 2001 – 76 с.
Отпечатано в ООО ПФ «Джуди», тираж. 200 экз.