Darmowe konto pozwoli wrócić do niego później.
Polecenie
Zadanie 2. Krajobraz
W pewnym paśmie górskim znajduje się n szczytów, które będziemy przedstawiać jako punkty w układzie kartezjańskim na płaszczyźnie. Wszystkie punkty leżą powyżej osi OX, tzn. druga współrzędna (y) każdego punktu jest dodatnia.
W punkcie (0,0) stoi obserwator. Jeśli dwa szczyty A i B mają współrzędne (xA, yA) oraz (xB, yB), to mówimy, że:
• szczyt A jest dla obserwatora widoczny na lewo od B, jeśli xA/yA < xB/yB;
• szczyt B jest widoczny na lewo od A, jeśli xA/yA > xB/yB.
Wiemy, że żadne dwa szczyty nie leżą w jednej linii z obserwatorem, a zatem dla obserwatora te szczyty nie zasłaniają się nawzajem.
Darmowe konto pozwoli wrócić do niego później.
Współrzędne szczytów dane są w dwóch tablicach X[1..n] oraz Y[1..n] – szczyt numer i ma współrzędne (X[i], Y[i]).
Zadanie 2.1.
Napisz algorytm (w pseudokodzie lub wybranym języku programowania), który znajdzie i poda współrzędne skrajnie lewego szczytu, tzn. widocznego dla obserwatora na lewo od wszystkich pozostałych szczytów.
Specyfikacja:
Dane:
n – liczba całkowita dodatnia
X[1..n] – tablica liczb całkowitych
Y[1..n] – tablica liczb całkowitych dodatnich
Para (X[i], Y[i]) to współrzędne jednego szczytu, i = 1, 2, …, n.
Żadne dwa szczyty nie leżą w jednej linii z obserwatorem.
Wynik:
x, y – współrzędne skrajnie lewego szczytu spośród tych opisanych w tablicach X i Y.
k ← 1
dla i = 2, 3, ..., n wykonuj
jeżeli X[i]/Y[i] < X[k]/Y[k]
k ← i
x ← X[k], y ← Y[k]
za poprawny algorytm, w tym:
za prawidłową inicjalizację oraz konstrukcję pętli,
za zastosowanie prawidłowego porównania oraz wyznaczenie współrzędnych skrajnie lewego szczytu.
Aby uniknąć dzielenia zmiennoprzecinkowego, można porównywać X[i]*Y[k] < X[k]*Y[i] zamiast X[i]/Y[i] < X[k]/Y[k], pamiętając że Y wartości są dodatnie.
Ocena według schematu punktowania CKE, zwykle w 15–30 s
Dowiedz się, ile punktów naprawdę zdobywasz. Zrób zdjęcie kartki albo wklej odpowiedź: Maturownik+ porówna ją ze schematem punktowania, policzy punkty i wytłumaczy, gdzie i dlaczego je tracisz.