NKSPILJA - Hang động
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+,N+}
PROGRAM NKSPILJA;
CONST
FINP='';
FOUT='';
oo=1000000;
maxn=5000;
max=1000000;
esp=0.005;
VAR
x,y:array[1..maxn] of double;
n:longint;
kq:double;
procedure readInput;
var
f:text;
i:integer;
begin
assign(f,FINP); reset(f);
read(f,n);
for i:=1 to n do
read(f,x[i],y[i]);
close(f);
end;
procedure writeOutput;
var
f:text;
begin
assign(f,FOUT); rewrite(f);
writeln(f,kq:0:2);
close(f);
end;
function ok(y0:double):boolean;
var
l,r,x0:double;
i:longint;
begin
l:=0; r:=max;
for i:=1 to n-1 do
if y[i]=y[i+1] then
begin
if y0<y[i] then begin l:=oo; r:=0; end;
end
else if y[i]>y[i+1] then
begin
x0:=(x[i]*y[i+1]-y[i]*x[i+1]-(x[i]-x[i+1])*y0)/(y[i+1]-y[i]);
if x0>l then l:=x0;
end
else if y[i]<y[i+1] then
begin
x0:=(x[i]*y[i+1]-y[i]*x[i+1]-(x[i]-x[i+1])*y0)/(y[i+1]-y[i]);
if x0<r then r:=x0;
end;
if l<r then ok:=true else ok:=false;
end;
procedure chia(y1,y2:double);
var
mid:double;
begin
mid:=(y1+y2)/2;
if ok(mid) then
begin
if mid-y1<esp then begin kq:=mid; writeOutput; halt; end;
chia(y1,mid);
end
else
begin
if y2-mid<esp then begin kq:=mid; writeOutput; halt; end;
chia(mid,y2);
end;
end;
BEGIN
readInput;
chia(0,oo);
END.