Otoczenie sadu
Limit pamięci: 32 MB
Bajtazar ma specyficzny sad, który chce otoczyć. Jest jednak niewyobrażalnie powolnym człowiekiem i nie nadąża za wciąż rosnącymi i umierającymi drzewami. Niestety, nie może się także zdecydować kiedy zacząć budowę ogrodzenia. Siedzi przy kominku długimi latami i rozważa jaką opcję wybrać. Wie tylko, że chce zbudować najkrótsze takie ogrodzenie, które otoczy wszystkie rosnące w jego sadzie, w danym momencie, drzewa. Bajtazar lubi chwalić się przed sąsiadami, więc w trakcie rozważań interesuje go, ile drzew będzie stało przy samym ogrodzeniu. Czasem może też zastanawiać się czy któreś konkretne (np. jego ulubione) drzewo znajdzie się na krawędzi otoczonego obszaru. Pomóż Bajtazarowi odpowiadać na te pytania. Możesz założyć, że drzewa reprezentowane są przez punkty na płaszczyźnie.
Zadanie
Napisz bibliotekę symbolizującą sad i udostępniającą następujące funkcjonalności:
- wzrost nowego drzewa na wschód (czyli z większą współrzędną
) od pozostałych (taka już specyfika tego sadu),
- Pascal: procedure dodaj( x: longint; y: longint )
- C/C++: void dodaj(int x,int y)
- obumarcie drzewa położonego najbardziej na zachód,
- Pascal: procedure usun()
- C/C++: void usun()
- zapytanie, czy
-te drzewo leży w tej chwili na brzegu najkrótszego ogrodzenia
- Pascal: function zapytanie( i: longint ):longint
- C/C++: int zapytanie(int i)
- zapytanie o ilość drzew leżących na brzegu najkrótszego ogrodzenia
- Pascal: function wielkosc():longint
- C/C++: int wielkosc()
Możesz założyć, że 
,
współrzędne 
kolejnych drzew będą tworzyły ciąg ściśle rosnący
oraz że 
będzie zawsze numerem aktualnie żywego drzewa
(drzewa numerowane są zgodnie z kolejnością ich dodawania, poczynając od 1),
a także, że usun() nigdy nie zostanie wywołane, gdy sad będzie pusty.
Łączna liczba wywołań funkcji i procedur z Twojej biblioteki nie przekroczy stu tysięcy.
Na dobry początek otrzymujesz pliki:
- oto.cpp, oto.c, oto.pas - pustą bibliotekę, gotową na zaimplementowanie w niej Twojego rozwiązania
- oto_zawodnik.cpp, oto_zawodnik.c, oto_zawodnik.pas - przykładowy program korzystający z Twojej biblioteki
- oto.h - nagłówek Twojej biblioteki w C/C++
Aby poprawnie skompilować swoje rozwiązanie należy użyć jednego z poleceń:
- g++ -O2 -static -lm oto_zawodnik.cpp oto.cpp -o oto
- gcc -O2 -static -lm oto_zawodnik.c oto.c -o oto
- ppc386 -O2 -XS oto_zawodnik.pas
Przykładowy przebieg
| Wywołanie funkcji | Zwracana wartość i wyjaśnienie |
| dodaj(1, 1); | Pierwsze drzewo. |
| dodaj(3, 3); | Drugie drzewo. |
| wielkosc(); | 2 Oba drzewa są w rogach ogrodzenia. |
| dodaj(4, 2); | Trzecie drzewo. |
| dodaj(6, 1); | Czwarte drzewo. |
| zapytanie(3); | 0 Trzecie drzewo leży obecnie wewnątrz trójkątnego ogrodzenia, a więc nie leży na krawędzi. |
| usun(); | Pierwsze drzewo umiera. |
| zapytanie(3); | 1 W tej chwili trójkątne ogrodzenie ma w rogach drzewa o numerach  ,  i  , a więc trzecie drzewo leży na krawędzi. |
Autor zadania: Jakub Pawlewicz.
<Wyślij rozwiązanie> [0/100]