Analiza

Umesto da posmatramo problem "iz perspektive kruga", nađimo za svaku pravu skup krugova imaju presek sa njom. Kako je ~i~-ti krug sadržan u narednom, ako prava seče ~i~-ti krug, tada sigurno seče i svaki naredni, što znači da ovaj skup krugova čini segment, pritom, sufiks, niza krugova. Nađimo, dakle, za svaku pravu najmanji krug koji se seče sa njom. Iz gore izloženog zaključujemo da se ovaj krug može naći binarnom pretragom po krugovima - ako se neki krug ne seče sa pravom, nastavljamo pretragu po većim krugovima, inače, pamtimo rešenje i tražimo među manjim krugovima. Nakon što smo našli indeks ~j~ ovog najmanjeg kruga, u nizu rešenja ~z~ treba brojevima ~z_j, z_{j+1}, \ldots, z_n~ da dodamo ~1~, što možemo uraditi tako što dodamo ~1~ broju ~z_j~ a nakon što obradimo sve prave izračunamo prefiksnu sumu niza ~z~, koju štampamo.

Smernice za algoritam

Da bismo ispitali da li se prava određena dvema tačkama ~A, B~ seče sa krugom radijusa ~r~ sa centrom u tački ~C~, najjednostavniji način je da nađemo udaljenost prave ~AB~ do tačke ~C~ i da taj broj uporedimo sa ~r~. Izračunajmo dvostruku površinu trougla ~ABC~ kao apsolutnu vrednost vektorskog proizvoda ~2P = |CA \times CB|~ i dužinu duži ~|AB|~. Kako je udaljenost prave ~AB~ od ~C~ zapravo visina trougla ~h_C~, tu visinu možemo izračunati preko površine: ~h_C = \frac{2P}{|AB|}~. Pritom, sve ove operacije se mogu pouzdano izračunati pomoću tipa double sa relativnom preciznošću ~10^{-14}~ što je dovoljno dobro za ovaj zadatak.