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 \neq p$ and $r \neq 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 $p q, p r$, and $q r$ :

Any line that do not pass through any of points $p, q, r$ meets the sides $p q, q r, p r$ of triangle $p q r$ 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 $p q r$.

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{aligned} 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 \quad(\bmod 2), \end{aligned}$$

and the result follows.