Macedonian Mathematical Competitions

Let the given points and the line be lying in the plane $\pi$. The line $p$ is dividing the plane into the two half-planes $\pi_1$ and $\pi_2$. If in one of the half-planes lies $m$ points, then in the other lies $2n - m$ points. A segment with endpoints in the same half-plane does not cut with the line. The line cuts only the segments with endpoints in the different half-planes. The number of these segments is $m(2n - m)$. Because $n^2 - m(2n - m) = n^2 - 2nm + m^2 = (n - m)^2 \ge 0$, we have $n^2 \ge m(2n - m)$. This means that the line is cutting no more than $n^2$ segments.