@Dimitar 16
Ja sam baš tako uradio. Graham scan za plave, zatim crvene, pa onda bruteforce. Ali ne radi na tri test primera. Evo i koda (nadam se da može nešto da se pročita):
Code:
program tacke;
const
maxn=100000;
type
tacka=record
x,y:real;
end;
niz=array[1..maxn] of tacka;
var
tp,tc,tp1,tc1:niz;
np,nc,n1p,n1c:longint;
max:real;
procedure ucitaj;
var
i:longint;
begin
readln(np);
for i:=1 to np do
readln(tp[i].x,tp[i].y);
readln(nc);
for i:=1 to nc do
readln(tc[i].x,tc[i].y);
end;
function sv(a,b,c:tacka):real;
begin
sv:=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
end;
function ras(a,b:tacka):real;
begin
ras:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
end;
procedure razmeni(var a,b:tacka);
var
p:tacka;
begin
p:=a;
a:=b;
b:=p;
end;
procedure qs(l,r:longint;var t:niz);
var
i,m:longint;
begin
if r=l+1 then begin
if sv(t[1],t[l],t[r])<0
then razmeni(t[l],t[r]);
end else begin
m:=l;
for i:=l+1 to r do
if sv(t[1],t[l],t[i])<0 then begin
inc(m);
razmeni(t[m],t[i]);
end;
razmeni(t[l],t[m]);
if l<m-1 then qs(l,m-1,t);
if m+1<r then qs(m+1,r,t);
end;
end;
procedure grahscan(n:longint;var t,t1:niz;var n1:longint);
var
i,k:longint;
begin
k:=1;
for i:=2 to n do
if (t[i].x<t[k].x) or ((t[i].x=t[k].x) and (t[i].y<t[k].y))
then k:=i;
razmeni(t[k],t[1]);
qs(2,n,t);
t1[1]:=t[1];
t1[2]:=t[2];
k:=2;
for i:=3 to n do begin
while (k>1) and (sv(t1[k-1],t1[k],t[i])<=0)
do dec(k);
inc(k);
t1[k]:=t[i];
end;
n1:=k;
end;
procedure resi;
var
i,j:longint;
begin
grahscan(np,tp,tp1,n1p);
grahscan(nc,tc,tc1,n1c);
max:=0;
for i:=1 to n1p do
for j:=1 to n1c do
if ras(tp1[i],tc1[j])>max
then max:=ras(tp1[i],tc1[j]);
writeln(max:0:3);
end;
begin
ucitaj;
resi;
end.
[Ovu poruku je menjao stf dana 15.10.2005. u 12:22 GMT+1]
If you don't live for something, you will die for nothing.