[ RooTeR @ 12.10.2005. 19:21 ] @
Zadatak glasi ovako :

dato je n crvenih i m plavih tacaka (m,n<= 100 000), i potrebno je naci najvece rastojanje izmedju dve tacke, tako da je jedna plava, a druga crvena.

[ cassey @ 12.10.2005. 21:13 ] @
Pa ja mislim da ce ovde dobro (koliko se secam) da radi to da nadjes konveksne pa ides redom, jer za N random tacaka broj tacaka u konveksnom bice (verovali ili ne) logN tako da je to verovatno dobro (to je bilo koliko se secam na neko SAV)...
Elem, najbolje resenje je smrt. Znaci nadjes konveksne i uzmes prvu tacku sa jednog i onda nedjes nenjgovu najudaljenjiu. E, sad rotiras ovaj prvi tako da se tako da "padane na sledecu starnicu" pa onda redom ali ne trazis sve neko samo levo od njegove najudaljenije.... Malo konfuzno ali sada cu da nadjem resenje sa Usaca (bio je on pre neku godinu pa cu da postujem njihovo zvanicno resenje)...
[ Srđan Krstić @ 12.10.2005. 21:55 ] @
Da, zadatak je sa saveznog od pre neku godinu. Na usaco je bio sa jednom bojom. Dakle kao sto je reko andrejko, nadjes konveksne omotace i random tacku na prvom pa njenu najudaljeniju na drugom, pa po jednom rotiras u jednom smeru po drugom u drugom, tako da ces za svaku tacku na prvom poligonu da nadjes njenu najudaljeniju na drugom. Ne znam zasto kazes verovali ili ne, broj tacaka na konveksnom poligonu je reda logN, postoji i dosta trivijalan dokaz ovoga, zato QuickHull radi u NlogN, cak i brze nego Graham Scan. Elem, resenje Aleksandra Ilica (cassey-evog brata): Kad si naso poligone, umesto rotacije, uzmes neku tacku na prvom, pa nadjes njenu najudaljeniju na drugom poligonu, pa od te tacke najudaljeniju na prvom, pa od nje na drugom, i kad odes i vratis se od jednog poligona ka drugom istom ivicom to je najvece rastojanje. Na svim test primerima je to bilo <10 setanja napred nazad :D:D
[ RooTeR @ 12.10.2005. 22:21 ] @
Bash je fino ovo reshenje sto Srdjan napisa ...
Hvala!
[ --SOULMaTe-- @ 14.10.2005. 00:03 ] @
Da, slazem se. Oba nacina su lepa.
[ stf @ 15.10.2005. 10:02 ] @
Koji algoritam je njabolje koristiti u ovom slučaju za traženje konveksnih omotača?
Ja sam na z-treningu koristio Graham Scan, ali ne može da prođe vremensko ograničenje od 4 sekunde.
[ dimitar 16 @ 15.10.2005. 10:10 ] @
Pa jas sam koristio graham scan i sve je proslo za pomalku
od 1sec.
Znaci nadjes konveksni omotac plave a potoa i na
crvene i so ednostaven bruteforce gi sporeduvas site rastojanija megu
tockite od dvata konveksni omotaca.
[ stf @ 15.10.2005. 11:21 ] @
@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]
[ dimitar 16 @ 15.10.2005. 14:58 ] @
Siguren sum deka algoritamot ne ti je tacno implementiran
pa ti producira poveke tocki odosto bi imal konveksniot omotac. Evo ti
moj kod, pa ga razgledaj:

Code:

program tacke;
uses math;
const maxn = 100000;
type point = record
                   x, y: longint;
                   t   : double;
             end;
var c, p, s: array [1..maxn] of point;
    f: text;
    n, m, i, j, kraj, min: longint;
    r, max : double;

procedure input;
begin
     assign (f, '');
     reset (f);

     readln (f, n);
     for i:= 1 to n do
         readln (f, c[i].x, c[i].y);

     readln (f, m);
     for i:= 1 to m do
         readln (f, p[i].x, p[i].y);

     close (f);
end;

procedure swap (var a, b: point);
var t: point;
begin
     t:= a; a:= b; b:= t;
end;

function theta (p1, p2: point): double;
var dx, dy, ax, ay: longint;
    t: double;
begin
     dx:= p2.x - p1.x;
     dy:= p2.y - p1.y;
     ax:= abs (dx);
     ay:= abs (dy);
     if (dx = 0) and (dy = 0) then
        t:= 0
     else
        t:= dy / (ax + ay);
     if dx < 0 then
        t:= 2 - t
     else if dy < 0 then
        t:= t + 4;
     theta:= 90 * t;
end;

procedure sort (l, r: longint; var p: array of point);
var i, j: longint;
    t, x: point;
begin
     i:= l; j:= r;
     x:= p[(l + r) div 2];
     repeat
           while (x.t>p[i].t) do inc (i);
           while (x.t<p[j].t) do dec (j);
           if i <= j then begin
              swap (p[i], p[j]);
              inc (i);
              dec (j);
           end;
     until i > j;
     if j > l then sort (l, j, p);
     if i < r then sort (i, r, p);
end;

function levo (p1, p2, p: point): boolean;
var t: longint;
begin
     t:= ((p.y - p1.y) * (p2.x - p1.x)) -
         ((p.x - p1.x) * (p2.y - p1.y));
     levo:= t > 0;
end;

procedure push (a: point);
begin
     inc (kraj);
     s[kraj]:= a;
end;

procedure graham (var a: array of point; var n: longint; isc: boolean);
var br: longint;
    t: point;
begin
     for i:= 1 to n-1 do
         if (a[min].y>a[i].y) or ((a[min].y=a[i].y) and (a[min].x>a[i].x)) then
            min:= i;
     swap (a[0], a[min]);
     for i:= 1 to n-1 do
         a[i].t:= theta (a[i], a[0]);

     sort (1, n, a);

     br:= 0;
     i:= 1;
     while i < n-1 do begin
         inc (br);
         t:= a[i];
         j:= i+1;
         while (j < n-1) and (a[j].t=t.t) do begin
               if a[j].x > t.x then
                  t.x:= a[j].x;
               inc (j);
         end;
         i:= j;
         a[br]:= t;
     end;

     kraj:= 0;
     min:= 0;
     push (a[0]);
     push (a[1]);
     push (a[2]);

     for i:= 3 to n-1 do begin
         while not levo (s[kraj-1], s[kraj], a[i]) do
               dec (kraj);
         push (a[i]);
     end;
end;

procedure solve;
begin
     if (n > 1000) and (m > 1000) then begin
           graham (c, n, true);
           n:= kraj;
           for i:= 1 to n do
               c[i]:= s[i];

           graham (p, m, false);
           m:= kraj;
           for i:= 1 to m do
               p[i]:= s[i];
     end;

     max:= 0;
     for i:= 1 to n do
         for j:= 1 to m do begin
             r:= hypot (abs (c[i].x-p[j].x), abs (c[i].y-p[j].y));
             if r > max then max:= r;
         end;

     writeln (max:0:3);
end;

begin
     input;
     solve;
end.