Ima li neko da mi predlozi ideju kako se resava zadatak?Ja sam mislio sledece,ali moja ideja ocigledno ne pije vodU(prolazi za 5 test primera):Pretpostavim da se sve tacke nalaze u nekom kvadratu dimenzija nxn(gde je meni n 2000000).Sada ako nadjem za svaki od skupova(plave i crvene tacke) one tacke koje su najblize gorenjem levom,gorenjem desnom,donjem levom i donjem desnom uglu tog kvadrata i onda sam mislio da sipitivanjem rastojanja samo izmedju njih mogu doci do resenja.Ovo ne valja.Kako bi trebao da ide otprilike algoritam.Neki hint,molim...
Dva konveksna omotacha ...
koja su ogranicenja za koordinate tacaka?
Ako netko moze pogledati ako sam uopce dobro shvatio ideju omotacima ovdje je kod
http://www.z-trening.com/new/www/html/submit.php?submit=7100012352&subm_code=1
Znaci nadjem sve vrhovi i samo medju njima trazim maks. udaljenost
Recimo da imam dvije konveksne ljuske, kako cu naci maksimalnu udaljenost izmedju dvije tocke? Mogao bi za svaku crvenu vidjeti koliko je udaljena od svake plave, ali to je u najgorem n * m ( ako nema niti jedne tocke unutar konveksnih ljusaka )
Ako se jedna ljuska ne nalazi unutar druge , najudaljenje tocke ce biti one na rubu tih ljusaka, a ako je jedna ljuska unutar druge onda ce biti jedna od onih koje su unutar manje ljuske, jel tako?
http://slike.hr/vidi.php?z=slika26.png
Recimo da imas ovakve ljuske ( s puno vise točaka ), kako bi našao tu udaljenost?
Što znači "na rubu"? Najdonja, najgornja itd?
ovo na rubu sam krivo napisao(nije na rubu ljuske ,nego je na ljusci) ,
Za ovu sliku, tražio bih udaljenost između svih točaka crvene i plave konveksne ljuske
