APMO

Choose any point $p$ from $S$ and color it, say, blue. Let $n(q,r)$ be the number of lines from $\mathcal{L}$ that separates $q$ and $r$. Then color any other point $q$ blue if $n(p,q)$ is odd and red if $n(p,q)$ is even.

Now it remains to show that $q$ and $r$ have the same color if and only if $n(q,r)$ is odd for all $q\ne p$ and $r\ne p$, which is equivalent to proving that $n(p,q)+n(p,r)+n(q,r)$ is always odd. For this purpose, consider the seven numbered regions defined by lines $pq,pr$, and $qr$ :



Any line that do not pass through any of points $p,q,r$ meets the sides $pq,qr,pr$ of triangle $pqr$ in an even number of points (two sides or no sides), so these lines do not affect the parity of $n(p,q)+n(p,r)+n(q,r)$. Hence the only lines that need to be considered are the ones that pass through one of vertices $p,q,r$ and cuts the opposite side in the triangle $pqr$.

Let $n_i$ be the number of points in region $i$, $p,q$, and $r$ excluded, as depicted in the diagram. Then the lines through $p$ that separate $q$ and $r$ are the lines passing through $p$ and points from regions 1, 4, and 7. The same applies for $p,q$ and regions 2, 5, and 7; and $p,r$ and regions 3, 6, and 7. Therefore

$$\begin{array}{rl}n(p,q)+n(q,r)+n(p,r)& \equiv \left(n_2+n_5+n_7\right)+\left(n_1+n_4+n_7\right)+\left(n_3+n_6+n_7\right)\\ & \equiv n_1+n_2+n_3+n_4+n_5+n_6+n_7=2004-3\equiv 1(\mathrm{mod}2),\end{array}$$

and the result follows.