Witam,
Chciałem zapytać jak sprawdzić mając n okręgów (z podanymi współrzędnymi środka i wielkości promienia) czy któryś z nich nachodzi na inny. Algorytm ma działać w czasie n * log(n), czyli jakoś muszę zmniejszać za każdym razem ilość okręgów do sprawdzenia i właśnie tu jest problem, bo nie bardzo mam pomysł. Myślałem o czymś typu zamiatanie polarne, ale nie wiem czy to coś pomoże. Jeśli można to prosiłbym o jakieś wskazówki.
0
0
Pierwsze co mi przychodzi do glowy to minimalne drzewo rozpinajce i sprawdzenie czy suma wag jego krawedzi jest < suma promieni kol, ale to bedzie mialo za wysoka zlozonosc ;]
0
Mamy trzy okręgi:
o1, o2, o3
Sprawdzasz:
Krok1:
- o1 koliduje z o2
- o1 koliduje z o3
Krok 2:
3) o2 koliduje z o3
4) z o1 nie musisz sprawdzać bo zostało to sprawdzone w punkcie 1
Krok 3:
5) z o1 sprawdzone w punkcie 2
6) z o2 sprawdzone w punkcie 3
0
cpper a co jesli nie beda kolidowac z niczym? wtedy masz zlozonosc n^n-1 (bo musisz wszystkie ze wszystkimi sprawdzic)
0
No ale to i tak zmniejszasz ilość sprawdzeń.
Jęśli o1 NIE koliduje z o2, to o2 też nie koliduje z o1
0
Hmm... wydaję mi się że tutaj chodzi o jakiś bardziej sprytny sposób niż ten który podałeś cpper, ten byłby zbyt prosty. A co do drzewa rozpinającego to faktycznie zbyt wysoką złożoność będzie miało
0
@Cpper ale co to ma do rzeczy w oglole? To co podales to jest najbardziej naiwny i oczywisty algorym o zlozonosci O(n^2)
1
Czy przypadkiem nie chodzi o to http://pastebin.com/gH40aQjR
Bo to nie są koła.
0
Doktor J. K. ???
0
To się chyba da zrobić metodą zamiatania - poczytaj o problemie rozstrzygnięcia, czy jakakolwiek para odcinków w zbiorze odcinków się przecina, tutaj będzie podobne rozwiązanie. Jeśli nie ma w necie materiałów to Cormen - Wprowadzenie do Algorytmów. Twój problem jest podobny i pewnie robi się go podobnie z pewnymi modyfikacjami - mam pewien pomysł na to ale nie jestem pewien czy dobry. W każdym razie, to zadanie było ćwiczeniem w Cormenie i może gdzieś wygooglujesz rozwiązanie.
0
Tak masz rację Pando. Jakby kolega porshelukas uważał na zajęciach to by pewnie wiedział żeby zamiatać miotełką.
0
IMO trzeba wykorzystać 2 fakty:
#metryka maksimum
#współrzędne i promienie są liczbami całkowitymi.
Te fakty pozwalają na zbudowanie mapy opisującej zajętą przestrzeń w rozsądnym rozmiarze pamięci.
Zapamiętywałbym dla x oraz dla y przedziały liczb i odpowiadające im indeksy kół.
0
mój pomysł wygląda tak: przybliżamy sobie okręgi kwadratami - jeśli kwadraty się nie nakładają, to zawarte w nich okręgi również.
potem tworzysz dwie tablice, posortowane odpowiednio po x-r (X), i y-r (Y) oraz listę W na wyniki.
jedziesz w pętli po kolei po wszystkich okręgach O:
{
binarnie wyszukujesz w X indeks okręgu O. konstruujesz hashtable H i wrzucasz do niej kolegów z lewej i prawej strony, spełniających warunek nakładania się współrzędnej x. jeśli kolega się nie nakłada lub osiągnąłeś któryś koniec tablicy X, to szukasz w drugim kierunku, potem kończysz szukanie.
binarnie wyszukujesz w Y indeks okręgu O. konstruujesz listę L i wrzucasz do niej kolegów z lewej i prawej strony, spełniających warunki nakładania się współrzędnej y i jednocześnie obecnych w hashtable H. jeśli kolega się nie nakłada lub osiągnąłeś któryś koniec tablicy Y, to szukasz w drugim kierunku a potem kończysz szukanie.
w pętli dla znalezionych okręgów weryfikujesz, czy faktycznie nakładają się (wcześniej przybliżaliśmy kwadratami) na O; nienakładające się usuwasz z L.
jeśli L jest niepuste, to do listy W dopisujesz O i zawartość L
jeśli chcesz zrobić optymalizację, to możesz usunąć z X i Y okrąg O (znasz indeks w obu tablicach po poprzednich krokach)
}
złożoność:
- dwa sortowania n*logn,
- n wyszukiwań logn,
- mn porównań dla kolegów i kn weryfikacji - tu jest słaby punkt algorytmu, jeśli większość okręgów przecina się ze sobą, to złożoność dąży do n^2, ale jeśli przecina się mało okręgów, to dąży do n
// edit
po zastanowieniu się dochodzę do wniosku, że algorytm w opisanej postaci nie da poprawnych wyników; dla x-r trzeba szukać x+r, a nie sąsiednie x-r. potem to samo trzeba zrobić dla x+r szukając x-r. dla y też trzeba zrobić analogiczną poprawkę.
być może problem rozwiążą jeszcze dwie tablice posortowane po x+r i y+r, ale już nie mam siły myśleć.
0
Możesz użyć zmodyfikowanej metody zamiatania (http://iair.mchtr.pw.edu.pl/~bputz/aisd_cpp/lekcja8/segment2/main.htm) generujesz odcinki ((x-r, y), (x+r, y)) i robisz tak jak byś sprawdzał czy się przecinają (tyle że nie sprawdzasz czy się przecinają tylko czy te powiązane z nimi okręgi nie nakładają się na siebie)