[ 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. |
[ RooTeR @ 12.10.2005. 19:21 ] @
[ 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. Copyright (C) 2001-2025 by www.elitesecurity.org. All rights reserved.
|