{ delphi } (* Problem: TABLE * Contest: UOI-2004 (Kharkiv) * Type: Solution * Author: Bogdan Yakovenko * Date: April 1, 2004 * Language: Pascal * Compiler: Delphi 5.0 * Algorithm: *) {$N+} const MAXN = 200; type crc = record x,y:real; end; var a:array[1..MAXN]of crc; b,e:array[1..MAXN]of byte; s1,s2:array[1..MAXN]of integer; h1,h2,i,j:integer; _r,n,gx1,gx2:longint; L,R,X:real; suxx:boolean; o:text; function dist(i,j:integer):byte; begin if sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y))-2*(_R+X)<=0 then dist:=1 else dist:=0; end; begin assign(o,'table.dat');reset(o); read(o,gx1,gx2); read(o,_R);read(o,N); for i:=1 to N do begin read(o,a[i].x,a[i].y); end; close(o); L:=0;R:=gx2-gx1; while abs(L-R)>0.00001 do begin X:=(L+R)/2; {} suxx:=false; for i:=1 to N do begin b[i]:=0;e[i]:=0;end; h1:=0;h2:=0; for i:=1 to N do if ((gx1+X)-(a[i].x-_R-X))>0 then begin inc(h1); s1[h1]:=i; b[i]:=1; end else begin inc(h2); s2[h2]:=i; end; for i:=1 to N do if ((a[i].x+_R+X)-(gx2-X))>0 then begin e[i]:=1;if b[i] = 1 then suxx:=true; end; { oldh2:=0;} if not suxx then begin i:=1; while (i<=h1) do begin j:=1; while (j<=h2) do begin if dist(s1[i],s2[j]) = 1 then begin if e[s2[j]] = 1 then suxx:=true; b[s2[j]]:=1; inc(h1);s1[h1]:=s2[j]; s2[j]:=s2[h2];dec(h2); end; if suxx then break; inc(j); end; if suxx then break; inc(i); end; end; if suxx then R:=X else L:=X; end; assign(o,'table.sol');rewrite(o); writeln(o,2*L:0:3); close(o); end.