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.

Download