[Algorytmy] Rezerwowanie punktów na płaszczyźnie

calmosc
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 4 cze 2013, o 15:28
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 8 razy

[Algorytmy] Rezerwowanie punktów na płaszczyźnie

Post autor: calmosc »

Cześć, problem polega na zwracaniu dla podanych współrzędnych punktu odpowiedzi na pytanie, czy dane miejsce (punkt) jest wolne, "Nie", jeśli punkt ten wcześniej był zaznaczony, czy też "zarezerwowany" i "Tak", jeśli w poprzednich wejściach nie był podany (inaczej: nie jest zarezerwowany), np. dla wejścia:

Kod: Zaznacz cały

1 0
2 1
3 5
1 0
2 2
powinien wyświetlić:

Kod: Zaznacz cały

Tak
Tak
Tak
Nie
Tak
Normalnie umieściłbym to w tablicy kwadratowej, ale współrzędne mogą przyjmować wartości co do modułu nie większe od \(\displaystyle{ 10^9}\), dlatego tablica zajmuje za dużo pamięci, nawet typu bool, a liczba punktów, które będą podane na wejściu nie przekracza 100000, więc to niedużo w porównaniu ze wszystkimi możliwymi punktami. Z tego co wiem odpowiedź "Tak" lub "Nie" nie musi być z tego powodu podawana w czasie stałym, ale liniowy jest za wysoki i trzeba tu sprawdzać rezerwację punktu logarytmicznie, nie bardzo wiem jak, ktoś ma jakiś pomysł? Byłbym wdzięczny.
SlotaWoj
Użytkownik
Użytkownik
Posty: 4211
Rejestracja: 25 maja 2012, o 21:33
Płeć: Mężczyzna
Lokalizacja: Kraków PL
Podziękował: 2 razy
Pomógł: 758 razy

[Algorytmy] Rezerwowanie punktów na płaszczyźnie

Post autor: SlotaWoj »

Dla zajętych punktów tylko lista ew. dwuwymiarowa tablica. Sprawdzasz, czy punkt jest na liście.
calmosc
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 4 cze 2013, o 15:28
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 8 razy

[Algorytmy] Rezerwowanie punktów na płaszczyźnie

Post autor: calmosc »

Sprawdzanie w czasie liniowym jest chyba za wolne, chyba że czegoś nie rozumiem.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Rezerwowanie punktów na płaszczyźnie

Post autor: Afish »

Masz masę struktur pozwalających na sprawdzenie istnienia elementu w czasie niższym od liniowego. Skiplista, sortowana tablica, zbalansowane drzewa BST i pewnie jeszcze wiele innych, do tego implementacja jest w każdym szanującym się języku programowania.
calmosc
Użytkownik
Użytkownik
Posty: 41
Rejestracja: 4 cze 2013, o 15:28
Płeć: Mężczyzna
Lokalizacja: Toruń
Podziękował: 8 razy

[Algorytmy] Rezerwowanie punktów na płaszczyźnie

Post autor: calmosc »

Nie bardzo wiem jak tu uwzględnić drugą współrzędną, tj. fakt że różnych punktów o wspólnej pierwszej współrzędnej może być więcej niż jeden.
Afish
Moderator
Moderator
Posty: 2828
Rejestracja: 15 cze 2008, o 15:45
Płeć: Mężczyzna
Lokalizacja: Seattle, WA
Podziękował: 3 razy
Pomógł: 356 razy

[Algorytmy] Rezerwowanie punktów na płaszczyźnie

Post autor: Afish »

Najpierw porównujesz po pierwszej współrzędnej, potem po drugiej.
ODPOWIEDZ