 |
 |
 |
Скачать программы Все программы автора
ЗАЛ КРУГЛЫХ СТОЛОВ
Единственный способ попасть в Зал Круглых Столов – пройти через Колонный Коридор. Стены Коридора изображаются на карте прямыми линиями, которые параллельны оси OY системы координат. Вход в Коридор находится снизу, а выход из Коридора в Зал – сверху. В Коридоре есть цилиндрические (на карте круглые) Колонны одинакового радиуса R.
Задание
Напишите программу TABLE, которая по информации о размерах Коридора, и размещения Колонн определяет диаметр наибольшего из Круглых Столов, который можно пронести через такой Коридор, сохраняя поверхность Стола горизонтальной.
Входные данные
В первой строке входного файла TABLE.DAT заданы два числа XL и XR – x-координаты левой и правой стен Коридора. Во второй строке находится целое число R (1≤R≤1 000 000) – радиус всех Колонн. В третей – целое число N (1≤N≤200), которое задает количество Колонн. Далее следуют N строк, в каждой из которых по два числа – x- и y-координаты центра соответствующей Колонны.
Все входные координаты – целые числа, которые по модулю не превосходят 1 000 000.
Выходные данные
Единственная строка выходного файла TABLE.SOL должна содержать одно число – искомый диаметр наибольшего Стола. Диаметр следует выводить с точностью 3 знака после десятичной точки (даже в случае, когда он окажется целым). Если нельзя пронести ни одного Стола, то ответ должен быть: 0.000
Точность 3 знака после точки, по обычным правилам округления, обозначает, что ответ, который выдается в выходной файл, должен отличаться от точного не более чем на 5×10-4 (т.е. на 0.0005). Например, если точный ответ 1.234567, то в файле должно находится число 1.235. Если точный ответ 5.0005, то необходимо округлять в большую сторону, т.е. в файл следует выдать 5.001
Пример входных и выходных данных
|
TABLE.DAT |
TABLE.SOL |
|
0 90 3 4 10 10 70 10 50 50 10 90 |
47.000 |
{ fp }
(* Problem: TABLE*)
const MAXN=500;
MAXM=3*MAXN;
EPS1=1e-4;
INFTY=1e30;
type Point=record
x,y:extended;
end;
var fv:text;
p:array[0..MAXM] of Point; {p[0] is special, temporary}
X_L,X_R,R_orig,R_curr:extended;
N,N_left_last,N_right_last:integer;
status:array[1..MAXM] of byte; {0/1/2, as Dijkstra; practically, only 1/2 used}
estim:array[1..MAXM] of extended;
procedure ReadData;
var i:integer;
Begin
assign(fv,'table.dat'); reset(fv);
readln(fv,X_L,X_R);
readln(fv,R_orig);
X_L:=X_L-R_orig;
X_R:=X_R+R_orig;
readln(fv,N);
for i:=1 to N do begin
readln(fv,p[i].x,p[i].y);
end;
close(fv);
End;
function dist_edge(v1,v2:integer):extended;
Begin
dist_edge:=sqrt(sqr(p[v1].x-p[v2].x)+sqr(p[v1].y-p[v2].y));
End;
function min(x,y:extended):extended;
Begin
if x<=y then min:=x else min:=y;
End;
function max(x,y:extended):extended;
Begin
if x>=y then max:=x else max:=y;
End;
procedure AddVirtualPoints;
var p_:Point;
i,j:integer;
R_:extended;
points_inside:boolean;
Begin
N_right_last:=N;
for i:=1 to N do begin
p_:=p[i];
p_.x:=(p_.x+X_R)/2;
p[0]:=p_;
R_:=(X_R-p_.x);
points_inside:=false;
for j:=1 to N do
if (j<>i) and (dist_edge(0,j)<=R_) then begin
points_inside:=true;
break;
end;
if not points_inside then begin
inc(N_right_last);
p[N_right_last].x:=X_R;
p[N_right_last].y:=p[i].y;
end;
end;
for i:=1 to N_right_last do begin
status[i]:=1;
estim[i]:=INFTY;
end;
N_left_last:=N_right_last;
for i:=1 to N do begin
p_:=p[i];
p_.x:=(p_.x+X_L)/2;
p[0]:=p_;
R_:=(p_.x-X_L);
points_inside:=false;
for j:=1 to N do
if (j<>i) and (dist_edge(0,j)<=R_) then begin
points_inside:=true;
break;
end;
if not points_inside then begin
inc(N_left_last);
p[N_left_last].x:=X_L;
p[N_left_last].y:=p[i].y;
status[N_left_last]:=2;
estim[N_left_last]:=0;
status[i]:=1;
estim[i]:=p[i].x-X_L;
end;
end;
End;
function SpreadLockingEdges:extended;
var the_est,est_,eee:extended;
i,j,k,v,u:integer;
Begin
the_est:=0;
while true do begin
est_:=INFTY;
for i:=1 to N_right_last do
if (status[i]=1) and (estim[i]<est_) then begin
est_:=estim[i];
v:=i;
end;
if est_>the_est then
the_est:=est_;
status[v]:=2;
if v>N then begin
SpreadLockingEdges:=the_est; exit
end;
for u:=1 to N_right_last do
if status[u]<>2 then begin
eee:=max(the_est,dist_edge(v,u));
if eee<estim[u] then
estim[u]:=eee;
end;
end;
End;
procedure WriteRes(D_curr:extended);
Begin
assign(fv,'table.sol'); rewrite(fv);
writeln(fv,D_curr-2*R_orig:0:3);
close(fv);
End;
BEGIN
ReadData;
AddVirtualPoints;
WriteRes(SpreadLockingEdges);
END.
|
|
|
