Editorial for Tangentni Četvorouglovi


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: Pajaraja

Vidimo da je od četvortke (a,b,c,d), a<b<c<d moguće napraviti tangentan četvorougao ako i samo ako a+d=b+c. Ovo važi jer u svakoj drugoj podeli po parovima jedan par je očigledno veći uod drugog (uverite se!). Stoga nam je zadatak ekvivalentan sa nalženjem broja rešenja a+d=b+c. Napišimo ovo kao a+d=b+c=x.

Te Sada ako za svako x izračunamo vrednost cnt[x], koji broj rešenja jednačine x=a+b, gde su a<b dužine nekih različitih plaidrvaca, možemo videti da će nam konačno rešenje biti \binom{cnt[1]}{2}+\binom{cnt[2]}{2}+\cdots+\binom{cnt[200000]}{2}, gde je \binom{x}{2}=\frac{x(x-1)}{2} broj načina da izaberemo dva od x brojeva. Ovo je validno jer je x ograničeno odozgo sa 2\cdot100000.

Ukupna vremenska složenost je O(N^2+MAX).


Comments

There are no comments at the moment.