[es] - [zadata] Najvece rastojanje izmedju datih tacaka ...

cassey
Andreja Ilic
Nis

Član broj: 57788
Poruke: 188
212.200.10.*

+1 Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{12.10.2005. u 21:13 - pre 225 meseci}

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)...

Math is like love. A simple idea but it can get complicated.

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.Princeton.EDU.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{12.10.2005. u 21:55 - pre 225 meseci}

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

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.dialup.neobee.net.

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{12.10.2005. u 22:21 - pre 225 meseci}

Bash je fino ovo reshenje sto Srdjan napisa ...
Hvala!

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Odgovor na temu

--SOULMaTe--
Nemanja Skoric
Novi Sad

Član broj: 1464
Poruke: 173
..mtsns-ns.customer.sbb.co.yu.

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{14.10.2005. u 00:03 - pre 225 meseci}

Da, slazem se. Oba nacina su lepa.

Don’t do drugs, sleep deprivation is better.

Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.172.EUnet.yu.

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{15.10.2005. u 10:02 - pre 225 meseci}

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.

If you don't live for something, you will die for nothing.

Odgovor na temu

dimitar 16
Dimitar Misev
Makedonija

Član broj: 31509
Poruke: 134
62.162.20.*

Jabber: dimitarmisev@gmail.com

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{15.10.2005. u 10:10 - pre 225 meseci}

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.

Odgovor na temu

stf

Član broj: 51276
Poruke: 65
*.155.EUnet.yu.

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{15.10.2005. u 11:21 - pre 225 meseci}

@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.

Odgovor na temu

dimitar 16
Dimitar Misev
Makedonija

Član broj: 31509
Poruke: 134
62.162.20.*

Jabber: dimitarmisev@gmail.com

Profil

Re: [zadata] Najvece rastojanje izmedju datih tacaka ...

^{15.10.2005. u 14:58 - pre 225 meseci}

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.

Odgovor na temu