Editorial for COCI '06 Contest 2 #4 Sjecišta


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.

Imagine that the polygon's vertices are labeled 0 to N-1 consecutively. Consider a diagonal from vertex 0 to some vertex i. Vertices 1 through i-1 are on one side of the diagonal, vertices i+1 through N-1 on the other. The diagonal intersects only those diagonals which have one vertex on one side and the other on the other side. Thus there are (i-1)(N-1-i) diagonals intersecting it.

We count all diagonals with one vertex being vertex 0 and multiply the number of diagonals by N (we could have labeled any vertex 0 and would get the same result). We counted each intersection on one diagonal twice (once from each vertex on a single diagonal) and each intersection a total of four times (because it lies on two diagonals). Hence we divide the result by 4.


Comments

There are no comments at the moment.