Step 1: forget the $2011$-gon and simply let there be $n$ points in the plane (no three collinear). Let the convex hull of these points be labeled clockwise $v_1,...,v_m$. Now suppose we colour the points red and blue such that there exists indicies $i<j<k<\ell$ with $v_i,v_k$ red and $v_j,v_{\ell}$ blue. Now any path between $v_i$ and $v_k$ will necessarily intersect a path $v_j$ to $v_{\ell}$. It follows that any good colouring of the $n$ points requires that $v_i,v_{i+1},...,v_j$ to be one colour, say red, for some $1\le i,j \le m$ and the rest of the vertices on the convex hull to be blue. Call such a colouring of the convex hull nice Proposition: Any colouring of $n$ points in the plane such that the convex hull is coloured nicely is a good colouring. Proof: We induct on the number of points. For $n=1,2,3$ the problem is trivial, so suppose it is true for $n=k\ge 3$ and consier $n=k+1$. Again let the vertices of the convex hull be $H=\{v_1,...,v_m\}$. If $H$ has vertices of both colours then we can find a point $v_i$ such that $v_{i-1}$ is one colour, say red, and $v_i,v_{i+1}$ are blue. If $H$ has vertices of only one colour then take any point $v_i$, which we can assume is also blue. Consider the convex hull of the $k$ points excluding $v_i$. If the hull is simply $H'=H\backslash\{v_i\}$ then we can remove $v_i$ and apply induction then add the edge $v_iv_{i+1}$. Otherwise $H' = (H\backslash{v_i} ) \cup \{p_1,...,p_j\}$ where the $p_i$ are some of the other points that weren't originally on the convex hull. If all the points $p_i$ are coloured red then the hull is still coloured nicely so we can remove $v_i$ and apply induction then add the edge $v_iv_{i+1}$. Otherwise there exists $p_{\ell}$ coloured blue. Now, no edge between two points in the plane can intersect the edge $p_{\ell}v_i$ because $p_{\ell}$ lies on the convex hull and $v_i$ is outside the hull. So we can remove $p_{\ell}$ and apply induction then add back the edge $v_ip_{\ell}$ without worrying about intersecting edges. It follows that the colouring of the $n$ points is good $\square$ All that is left to do is count the number of such colouring for $n=4022, \, m=2011$. If $H$ conatins both red and blue points then the first red point $v_i$ can be chosen in $2011$ ways. Then $v_i,v_{i+1},...,v_j$ are all red where $j$ can be one of $2010$ points (maybe $j=i$, but not $j=i-1$ else all points are red). On the other hand $H$ can be coloured with one colour in $2$ ways. This gives a total of $2011\cdot 2010+2$ colourings of $H$. The other points may be coloured in $2^{2011}$ ways. In total that's $(2011\cdot 2010+2)2^{2011}$ good colourings. In general for $m$ points on the convex hull and $k$ points on the interior there are $\left(\binom{m}{2}+1\right)2^{k+1}$ good colourings.

Another solution which first proves for triangles, then inducts via triangulations instead of removing vertices. We claim that the answer is $2^{2011}(2010*2011 + 2).$ Notice that it's clear that there cannot exist any quadrilateral among the $2011$ vertices of the $2011-$gon for which opposite vertices are similarly colored (i.e., blue-red-blue-red or red-blue-red-blue in clockwise order). This then implies that the blue vertices on the boundary must be contiguous, and similarly for red vertices, immediately implying the upper bound ($2^{2011}$ ways to color the things on the inside and $2010*2011 + 2$ ways to color the boundary). Now, we will show that any coloring satisfying the condition above indeed works. In fact, we will show that any coloring on any $m-$gon with $n$ interior vertices satisfying that its $m$ vertices are colored s.t. the blue and red vertices are contiguous admits a way of "connecting" with line segments as desired in the question. We'll first show a lemma: $\mathbf{Lemma.}$ Any triangle with two vertices of one color and one vertex of the other color with any number of interior points admits a desired connecting. $\mathbf{Proof.}$ We will prove the desired statement by induction on the number of interior points of the triangle. If there are no interior points, we are trivially done. Otherwise, suppose that there is at least one interior point, and that WLOG the triangle has two red vertices and one blue vertex, say $A, B$ are red, $C$ is blue. Then if $P$ in its interior is blue, then by splitting into $\triangle APB, \triangle BPC, \triangle APC$, we can easily finish from here by induction. Otherwise, every point inside is red, and we are trivially done here too. $\blacksquare$ Now, we will return to the claim at hand, which we'll prove with induction. If $m+ n = 3,$ then we're clearly done, as we have just a triangle with $0$ interior points. Now suppose that the induction hypothesis holds when $m + n < k$. When $m + n = k,$ we'll consider two cases. $\mathbf{Case}$ $\mathbf{1.}$ All $m$ vertices are colored the same way, WLOG blue: Let its vertices be $P_1, P_2, \cdots P_m$ and suppose that there is a point inside this polygon which is red, say $P$. Then, simply split into $\triangle PP_1P_2, \triangle PP_2P_3, \cdots, \triangle PP_{m-1}P_m, \triangle PP_mP_1,$ and apply the lemma on each triangle. Else, if all interior points are blue, we are trivially done too. $\mathbf{Case}$ $\mathbf{2.}$ There are points of both colors on its perimeter: Then, we can easily triangulate the $m-$gon into $m-2$ triangles such that each of them has $2$ of one color and $1$ of the other, and so applying the lemma on each of these triangles finishes. As the induction is complete, we can simply apply it when $m = 2011, n = 2011$ to get the desired answer. $\square$