Editorial for Astrologija


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: TadijaSebez

Posmatrajmo dva trougla koja se ne seku. Spojimo pravama svako teme prvog trougla sa svakim temenom drugog. Tačno dve među ovim pravama dele ravan na dve poluravni tako da se jedan trougao nalazi u jednoj, a drugi u drugoj. Ako se trouglovi seku očigledno ne postoji prava koja na ovaj način deli trouglove. Zadatak ćemo rešiti tako što ćemo za svake dve tačke A i B naći koliko postoji parova trouglova tako da je A teme prvog, B teme drugog i prava AB razdvaja ove trouglove. Ovo ćemo efikasno prebrojati tako što za svaku tačku A procesiramo tačke B redom po uglu i u svakom trenutku pamtimo koliko ima tačaka svake boje sa jedne i sa druge strane prave AB. Kada se pomeramo sa jedne tačke na drugu tačno jedna tačka menja stranu pa se jedno pomeranje može rešiti u O(1). Na kraju rešenje delimo sa 4 jer smo svaku pravu brojali dva puta i za svaki par trouglova postoje dve prave.

Vremenska složenost je O(N^2 logN) jer za svaku tačku sortiramo sve ostale tačke po uglu u O(NlogN).

Zadatak je preuzet sa \texttt{JOI} \texttt{Spring} \texttt{Training} \texttt{Camp} \texttt{2014}.


Comments

There are no comments at the moment.