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$ $0$ to $N-1$ $N - 1$ consecutively. Consider a diagonal from vertex $0$ $0$ to some vertex $i$ $i$ . Vertices $1$ $1$ through $i-1$ $i - 1$ are on one side of the diagonal, vertices $i+1$ $i + 1$ through $N-1$ $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)$ $(i - 1) (N - 1 - i)$ diagonals intersecting it.

We count all diagonals with one vertex being vertex $0$ $0$ and multiply the number of diagonals by $N$ $N$ (we could have labeled any vertex $0$ $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$ $4$ .

Comments

There are no comments at the moment.