Solution Notes (Bruce Merry):

The first reaction may be to use the winding number: if the rope has a non-zero winding number around a pole, then that pole obviously needs to be removed. However, this is not necessarily sufficient: in the sample case, the rope has a zero winding number around each pole, yet at least one pole must be removed. What's more, the sample case shows that testing each pole independently will not be good enough, because either pole can be left in place if the other is removed.

Thus, something smarter is required. The limit of 10 poles is a strong hint: we should have time to just try removing every subset, and then test whether the remaining poles leave Bessie free.

The geometry can get very messy, so let's try to simplify things. How can we use the fact that all the poles are in a line? Well, whatever happens entirely on one side of the line is irrelevant, since no matter how complex the shape it can always be straightened out without crossing any of the poles. So the only interesting segments are those that cross the line of poles. We can thus describe the rope by the sequence of points at which it crosses the pole line. The exact y coordinate is not relevant: only the position relative to the poles matters.

Now that we've simplified the representation of the rope, how can we move it around to release Bessie? Well, if the rope crosses at some point, and immediately afterwards crosses back at the same point, this is a loop that is not wrapped around any pole and can be pulled straight, making the two crossings disappear. If we represent each crossing point as a letter and the rope as a string (no pun intended) then this means we can delete any pair of adjacent letters that are the same e.g. abcxxdef -> abcdef. Conversely, we can of course insert two of the same letter anywhere into the sequence, but that turns out not to be useful.

Testing whether a particular set of poles allows Bessie to escape is now easy: take the starting string, and remove pairs of adjacent equal letters until either the string is empty (Bessie escapes) or there are no more pairs to remove (Bessie is stuck). This can be done in a single pass using a stack: each time a letter is seen, either pop from the stack if the new letter matches the top of the stack, or push the new letter onto the stack if not. The algorithm thus requires O(2^N.M) time.

#include <fstream>
#include <algorithm>
#include <complex>
#include <vector>

using namespace std;

typedef complex<int> pnt;

static int cross(const pnt &a, const pnt &b) { return imag(conj(a) * b); }
static int cross(const pnt &a, const pnt &b, const pnt &c)
{
    return cross(b - a, c - a);
}

int main()
{
    ifstream in("tied.in");
    ofstream out("tied.out");
    int N, M;
    int bx, by;
    in >> N >> M >> bx >> by;
    pnt B(bx, by);
    vector<pnt> pnts(N);
    for (int i = 0; i < N; i++)
    {
        int x, y;
        in >> x >> y;
        pnts[i] = pnt(x, y);
    }

    vector<pnt> rope(M + 1);
    for (int i = 0; i <= M; i++)
    {
        int x, y;
        in >> x >> y;
        rope[i] = pnt(x, y);
    }

    int px = pnts[0].real();
    vector<int> cuts;
    for (int i = 0; i < M; i++)
    {
        if ((rope[i].real() > px) ^ (rope[i + 1].real() > px))
        {
            int c = 0;
            for (int j = 0; j < N; j++)
                if (cross(rope[i], rope[i + 1], pnts[j]) > 0)
                    c++;
            if (rope[i + 1].real() > px)
                c = N - c;
            cuts.push_back(c);
        }
    }

    vector<int> st;
    st.reserve(cuts.size() + 1);
    int ans = N;
    for (int b = 1; b < (1 << N); b++)
    {
        int G = 0;
        vector<int> grp(N + 1);
        grp[0] = 0;
        for (int i = 0; i < N; i++)
        {
            if (b & (1 << i))
                G++;
            grp[i + 1] = G;
        }

        st.clear();
        for (int i = 0; i < (int) cuts.size(); i++)
        {
            int g = grp[cuts[i]];
            if (!st.empty() && g == st.back())
                st.pop_back();
            else
                st.push_back(g);
        }
        if (st.empty())
            ans = min(ans, N - __builtin_popcount(b));
    }
    out << ans << endl;
}