Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
перпендикуляра и прямой, координаты самой ближней к прямой
точки .
б) Существует третья точка, для которой выполняется условие:
перпендикуляр из этой точки к прямой и отрезки , соединяющие эту
точку с двумя заданными, образуют угол 120 градусов. На выходе:
длина перпендикуляра + сумма расстояний, координаты третьей
точки и ее проекции на прямую.
в) аналогично 1).
3. Программная реализация
Program Tubes; {Автор Поляков А.Е.}
Var X1,Y1,X2,Y2,A,B,C:LongInt;
Procedure Init;
{Инициализация}
Var F:Text;
Begin
Assign(F,'input.txt');ReSet(F);
ReadLn(F,A,B,C);
ReadLn(F,X1,Y1);
ReadLn(F,X2,Y2);
Close(F)
End;
Function TestLocation:Boolean;
{Проверка местонахождения заданных точек
Возвращает True, если точки расположены с одной стороны , и
False в противном случае }
Begin
TestLocation:=(A*X1+B*Y1+C)*(A*X2+B*Y2+C)>0
End;
Function Dest(X,Y:Double):Double;
{Вычисление длины вектора}
Begin
Dest:=Sqrt(Sqr(X)+Sqr(Y))
End;
Procedure Proj(X,Y:Double;Var TX,TY:Double);
{Вычисление проекции точки (X,Y) на прямую}
Begin
TX:=(-C*A+Sqr(B)*X-A*B*Y)/(Sqr(A)+Sqr(B));
TY:=(-C*B-A*B*X+Sqr(A)*Y)/(Sqr(A)+Sqr(B));
End;
Function FindDifferentSideDest(Var tx1,Ty1,Tx2,ty2:Double):Double;
{Решение задачи для случая 1}
Var D:Double;
Begin
Proj(X1,Y1,Tx1,Ty1);
D:=Dest(TX1-X1,TY1-Y1);
Proj(X2,Y2,Tx2,Ty2);
FindDifferentSideDest:=D+Dest(TX2-X2,TY2-Y2)
End;
Procedure FindPoint(PX,PY,X,Y,D:Double;Var TX,TY:Double);
{Нахождение координат точки на прямой, из которой точка (x,y)
видна под углом 30 градусов}
Var TX1,TX2,TY1,Ty2,Sq:Double;
Begin
Sq:=sqrt(3)*D/Sqrt(Sqr(A)+Sqr(B));
TX1:=PX+B*sq;TY1:=PY-A*Sq;
TX2:=PX-B*Sq;TY2:=PY+A*Sq;
PX:=Dest(TX1-X,Ty1-Y);
PY:=Dest(TX2-X,Ty2-Y);
If Px<Py Then Begin Tx:=Tx1;Ty:=Ty1 End
Else Begin Tx:=Tx2;Ty:=Ty2 End
End;
Function FindOneSideDest(Var tx1,Ty1,Tx2,ty2:Double):Double;
{Решение задачи для случая 2}
Var D1,D2,PX1,PY1,Px2,Py2,LX1,LY1,LX2,LY2,T,Res:Double;
Begin
Proj(X1,Y1,PX1,PY1);
D1:=Dest(PX1-X1,PY1-Y1);
FindPoint(PX1,PY1,X2,Y2,D1,Lx1,Ly1);
Proj(X2,Y2,PX2,PY2);
D2:=Dest(PX2-X2,PY2-Y2);
FindPoint(PX2,PY2,X1,Y1,D2,Lx2,Ly2);
{Случай 2 в}
Res:=D1+D2;
Tx1:=Px1;Ty1:=Py1;Tx2:=Px2;Ty2:=Py2;
{Случай 2 а}
T:=Dest(X2-X1,Y2-Y1);
If (D2>T) or (D1>T) Then
If D1>D2 Then Begin
Tx1:=x2;ty1:=Y2;Tx2:=Px2;Ty2:=Py2;Res:=D2+T End
Else Begin
Tx1:=x1;ty1:=Y1;Tx2:=Px1;Ty2:=Py1;Res:=D1+T End;
{Случай 2 б}
T:=Dest(LX1-LX2,LY1-LY2)/2;
T:=T/sqrt(3);PX1:=Dest(Lx1-X1,Ly1-Y1);PY1:=Dest(Lx2-X2,Ly2-
Y2);
If (2*T < PX1) and (2*T < PY1) and
(Dest(Lx2-X1,Ly2-Y1)<PY1) and (Dest(Lx1-X2,Ly1-Y2)<PX1) then
Begin
Px1:=(Lx1+Lx2)/2;Py1:=(Ly1+Ly2)/2;
Px2:=Px1-
T*A/Sqrt(Sqr(A)+Sqr(B));Px1:=Px1+T*A/Sqrt(Sqr(A)+Sqr(B));
PY2:=Py1-
T*B/Sqrt(Sqr(A)+Sqr(B));PY1:=Py1+T*B/Sqrt(Sqr(A)+Sqr(B));
T:=2*(D1+D2)-3*T;
If Res>T Then Begin
Res:=T;
If (A*PX1+B*PY1+C)*(A*X2+B*Y2+C)>0 Then
Begin Tx2:=Px1;Ty2:=Py1 End
Else Begin Tx2:=Px2;Ty2:=Py2 End;
Tx1:=(Lx1+Lx2)/2;Ty1:=(Ly1+Ly2)/2
End
End;
FindOneSideDest:=Res
End;
Procedure Done;
{Вывод результатов}
Var F:Text;Tx1,Ty1,tx2,ty2,D:Double;
Begin
Assign(F,'output.txt');ReWrite(F);
If not TestLocation Then D:=FindDifferentSideDest(Tx1,Ty1,Tx2,Ty2)
Else D:=FindOneSideDest(Tx1,Ty1,Tx2,Ty2);
WriteLn(F,D:1:4);
WriteLn(F,Tx1:1:4,' ',Ty1:1:4);
WriteLn(F,Tx2:1:4,' ',Ty2:1:4);
Close(F)
End;
Begin
Init;
Done
End.
Задача 6. "Телебашня "
Задача была предложена на общеуниверситетской олимпиаде
по программированию , посвящённой дню рождения факультета
ПММ (март 2001). Ниже приводится решение победителя
олимпиады , в настоящее время студента 4 курса факультета
ПММ ВГУ Михаила Михайловича Ширяева
1. Условие задачи .
В результате пожара полностью сгорела телевизионная башня
города Обломова, и всё население города осталось без
телевидения. Чтобы восстановить телевещание в кратчайшие
сроки , мэр города распорядился разместить передатчики на
крышах некоторых домов. Однако ситуация осложняется наличием
в городе нескольких небоскрёбов, владельцы которых установили у
себя на крыше антенну спутниковой системы See++ и поэтому не
дают согласия на установку там передатчиков. Более того , эти
небоскрёбы являются преградой на пути распространения сигнала ,
поэтому установки одного передатчика может оказаться
недостаточно. Мэр хочет установить минимальное количество
передатчиков так, чтобы зоны распространения сигнала покрывали
весь город , исключая, возможно, территорию, занимаемую
упомянутыми выше небоскрёбами.
Город Обломов представляет собой прямоугольник кварталов.
Все кварталы имеют форму квадрата равной площади, а ширина
улиц незначительна по сравнению с размерами квартала . Каждый
небоскрёб занимает полностью один квартал.
Каждый квартал (кроме небоскрёбов) имеет единственную
телевизионную антенну точно в центре , и считается охваченным
телевещанием , если существует какой-нибудь передатчик, который
находится в прямой видимости от антенны . Передатчики могут
располагаться только точно в центре квартала .
Сигнал распространяется строго по прямой. Если на пути от
передатчика к антенне сигнал лишь касается небоскрёба , сигнал
доходит до антенны . Других небоскрёбов в городе нет. Квартал, в
котором установлен передатчик, считается охваченным
телевещанием .
Программа должна найти минимальное количество
необходимых передатчиков и указать места их размещения.
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Время тестирования: 20 сек/тест
Входные данные:
Первыми задаются два числа от 1 до 14, которые определяют
количество кварталов в городе с запада на восток по оси x и с юга
на север по оси y соответственно. Далее идет число от 1 до 195,
задающее количество кварталов, занятых небоскрёбами, после чего
перечисляются пары x, y координат кварталов. Координаты
кварталов отсчитываются от 1.
Все числа во входных данных разделяются произвольным
количеством пробельных символов. В городе существует хотя бы
один квартал (дом мэра), не являющийся небоскрёбом .
Результат
Программа должна напечатать минимальное необходимое
число передатчиков, после чего перечислить координаты
кварталов, в которых они должны быть установлены .
2. Алгоритм решения.
Алгоритм основан на рекурсии. На каждом её шаге на карту
ставится антенна и вычисляются кварталы , охваченные вещанием .
Если до всех кварталов доходит сигнал, то расположение антенн
запоминается, при условии, что до этого не найдено расположение
с меньшим числом антенн.
Для хранения информации о расположении антенн,
небоскрёбов и кварталов, охваченных вещанием , используются
множества. Кроме того , информация о расположении небоскрёбов
дублируется в массиве , что позволяет ускорить работу программы.
3. Программная реализация
program Town; {Автор - Ширяев М.М.}
const
Nmax=14; {макс . число кварталов по горизонтали <=16}
Mmax=14; {по вертикали <=16}
Lmax=Nmax*Mmax; {макс . число кварталов}
type
TNum=1..Lmax; {тип индексов кварталов}
TSet=set of TNum; {тип множества кварталов}
TRec=record {координаты квартала }
x,y:integer
end;
TArr=array[TNum]of TRec;
var
neb, {множество небоскрёбов}
ant:TSet; {множество антенн}
arr_neb:TArr; {массив небоскрёбов}
n,m, {число кварталов по горизонтали и вертикали }
neb_num, {число небоскрёбов}
ant_num:integer; {число антенн}
function GetIndex(x,y:integer):integer;{индекс квартала }
begin
GetIndex:=(y-1)*Nmax + x
end;
procedure GetCoord(a:integer;var x,y:integer); {поиск координат
квартала }
begin
x:=(a-1) mod Nmax + 1;
y:=(a-1) div Nmax + 1
end;
procedure Load;{загрузка карты }
var
f:text;
i:integer;
begin
neb:=[];
Assign(f,'input.txt');Reset(f);
read(f,n,m,neb_num);
for i:=1 to neb_num do with arr_neb[i] do
begin
read(f,x,y);
neb:=neb+[GetIndex(x,y)]
end;
Close(f)
end;
procedure Save;{запись числа и расположения антенн}
var
f:text;
i,x,y:integer;
begin
Assign(f,'output.txt');Rewrite(f);
writeln(f,'Число антенн:');
writeln(f,ant_num);
writeln(f,'Координаты антенн:');
for i:=1 to Lmax do
if i in ant then
begin
GetCoord(i,x,y);
writeln(f,x,' ',y)
end;
Close(f)
end;
function Wave(a1,a2:integer):boolean;
{проходит ли волна между кварталами a1 и a2}
const
eps=0.01;{допустимое отклонение от угла квартала }
half=0.5-eps;
var
x1,y1,x2,y2,x,y,{координаты кварталов a1, a2 и проверяемого
небоскрёба}
i,t:integer;
k{коэффициент наклона прямой},p1,p2{точки пересечения с
небоскрёбом }:real;
begin
Wave:=true;
GetCoord(a1,x1,y1);
GetCoord(a2,x2,y2);
if x1=x2 then
begin
if y1>y2 then
begin
t:=y1; y1:=y2; y2:=t
end;