Da li neko moze da mi kaze smernice sa resavanje zadatka Krug sa SIO 2016 za srednje skole?
1 Like
U 2N upita cemo odrediti polozaje svih tacaka. Uzmimo proizvoljnu tacku a i pitajmo za rastojanja D(a, x) za sve tacke x. Neka je y najbliza tacka x – samim tim, garantovano je da su susedne. Neka su im pozicije 0 i D(x,y).
Sada za sve preostale tacke mozemo da pitamo za rastojanje D(y,z) i na osnovu njega odredimo relativni polozaj z u odnosu na x:
- ako D(y,z) = D(y,x) + D(x,z), z je sa suprotne strane x od y, i pozicija joj je -D(x,z)
- u suprotnom, sa iste je strane kao y i pozicija joj je D(x,z)
Za sada smo iskoristili N-1 + N-2 upita.
Jedino sto nam nedostaje je da odredimo obim kruga. Neka je l “najlevlja” tacka (sa najmanjom pozicijom) a r “najdesnija”. Pitamo za rastojanje D(l,r). Sada ili:
- D(l,r) = D(l,x) + D(x,r) – sve tacke su na jednoj polovini kruga. Ne znamo obim, ali l i r su najdalji par.
- U suprotnom, obim je D(l,r) + D(r,x) + D(x,l)
Ukupan broj upita: 2N - 2.
Ostaje da nadjemo najblizi i najdalji par u \mathcal{O}(N \log{N}). Sortiramo sve pozicije, i za najblizi par samo probamo sve susedne parove, a za najdalji primenjujemo two-pointer pristup: prolazimo kroz sortirani niz i odrzavamo indeks najdalje tacke (na drugom kraju kruga).
2 Likes