| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴下pascal代码const
inf=1e9;
eps=1e-7;
maxn=10010;
type
vector=record
x,y:double;
end;
arr=array[0..maxn*2] of vector;
var
a,b:arr;
n,m,i,j:longint;
ans:double;
operator +(a,b:vector)c:vector;
begin
c.x:=a.x+b.x; c.y:=a.y+b.y;
end;
operator -(a,b:vector)c:vector;
begin
c.x:=a.x-b.x; c.y:=a.y-b.y;
end;
function min(x,y:double):double;
begin
if x>y then min:=y else min:=x;
end;
function dis(a:vector):double;
begin
dis:=sqrt(a.x*a.x+a.y*a.y);
end;
function dot(a,b:vector):double;
begin
dot:=a.x*b.x+a.y*b.y;
end;
function cross(a,b:vector):double;
begin
cross:=a.x*b.y-a.y*b.x;
end;
function getdis(a,b,c:vector):double;
begin
if (dot(a-b,c-b)<-eps) or (dot(b-c,a-c)<-eps)
then getdis:=inf
else getdis:=abs(cross(b-a,c-a))/dis(b-c);
end;
procedure swap(var a,b:vector);
var
temp:vector;
begin
temp:=a; a:=b; b:=temp;
end;
function findmin(a:arr;n:longint):longint;
var
num,i:longint;
begin
num:=1;
for i:=2 to n do
if a[i].y<a[num].y then num:=i;
findmin:=num;
end;
function findmax(a:arr;n:longint):longint;
var
num,i:longint;
begin
num:=1;
for i:=2 to n do
if a[i].y>a[num].y then num:=i;
findmax:=num;
end;
procedure qsort(var a:arr;l,r:longint);
procedure sort(l,r:longint);
var
i,j:longint;
mid:vector;
begin
i:=l; j:=r; mid:=a[(i+j) shr 1];
repeat
while cross(a[i],mid)>0 do inc(i);
while cross(mid,a[j])>0 do dec(j);
if not (i>j)
then begin swap(a[i],a[j]); inc(i); dec(j); end;
until i>j;
if i<r then sort(i,r);
if j>l then sort(l,j);
end;
begin
sort(l,r);
end;
procedure graham(var a:arr;n:longint);
var
num,i:longint;
temp:vector;
begin
num:=findmin(a,n); swap(a[1],a[num]); temp:=a[1];
for i:=1 to n do a[i]:=a[i]-temp;
qsort(a,2,n);
for i:=1 to n do a[i]:=a[i]+temp;
end;
procedure solve(a:arr;n,h:longint;b:arr;m,j:longint);
var
i:longint;
begin
for i:=h to h+n-1 do
begin
while (cross(a[i+1]-a[i],b[j+1]-b[j])>0) do inc(j);
ans:=min(ans,dis(b[j]-a[i]));
ans:=min(ans,dis(b[j]-a[i+1]));
ans:=min(ans,dis(b[j+1]-a[i]));
ans:=min(ans,dis(b[j+1]-a[i+1]));
ans:=min(ans,getdis(b[j],a[i],a[i+1]));
ans:=min(ans,getdis(b[j+1],a[i],a[i+1]));
end;
end;
begin
while true do
begin
readln(n,m);
if n=0 then halt;
for i:=1 to n do readln(a[i].x,a[i].y);
for i:=1 to m do readln(b[i].x,b[i].y);
graham(a,n);
graham(b,m);
ans:=inf;
for i:=n+1 to n*2 do a[i]:=a[i-n];
for i:=m+1 to m*2 do b[i]:=b[i-m];
solve(a,n,findmin(a,n),b,m,findmax(b,m));
solve(b,m,findmin(b,m),a,n,findmax(a,n));
writeln(ans:0:5);
end;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator