Algoritmi → Binarna pretraga → Kružne zone – uputstvo

Kružne zone – uputstvo

Postavka

Meta se sastoji od n kružnih zona oko koordinatnog početka. Prva zona je krug, a svaka sledeća je kružni prsten oko prethodne. Zadate su širine zona redom od centra ka spolja. Za svaku od m tačaka (x, y) ispiši redni broj zone u kojoj se nalazi (zone se broje od 0) ili izvan ako je tačka van svih zona. Tačka na granici dve zone pripada unutrašnjoj zoni.

Ulaz: broj n, zatim n širina; broj m, zatim m parova koordinata (n, m ≤ 50 000).

Napomena: postavka je zapisana na osnovu postojećeg rešenja zadatka.

3
1 2 3
5
0 0
1 0
2 2
5 0
6 1

0
0
1
2
izvan

Uputstvo

1. Od širina do poluprečnika. Unose se širine prstenova, a za proveru nam trebaju poluprečnici spoljnih granica. Poluprečnik granice zone i je zbir širina zona 0..i: r[i] = r[i − 1] + širina[i]. Pošto su širine pozitivne, niz r je rastući – što omogućava binarnu pretragu.

2. Rastojanje tačke. Tačka (x, y) je udaljena od centra R = √(x² + y²).

3. Koja zona? Tačka je u zoni z ako je r[z − 1] < R <= r[z] (za z = 0 donja granica je 0). Dakle z je prva pozicija u nizu r na kojoj je r[z] >= R. Nju nalazimo binarnom pretragom ili funkcijom lower_bound. Ako takve pozicije nema, tačka je izvan mete.

4. Složenost. Za svaku tačku binarna pretraga radi log₂ n ≈ 16 koraka, ukupno O(m log n). Linearna provera svih zona bila bi O(m · n) = 2,5 · 10⁹ – prespora.