Essa questão foi resolvida usando:
Geometria computacional
Grafos bipartidos
Max-flow
Segue a explicação do problema (um pouco longa):
Você pode usar o algoritmo do livro de competitivo programming 3 para verificar se um ponto está dentro do polígono. Porém, no algoritmo do livro, se o ponto estiver exatamente na borda, ele considera que está fora do polígono. É preciso modificar isso para funcionar nesse problema. Para considerar como dentro o ponto da borda, é preciso verificar se o ponto pertence ao segmento que está sendo avaliado naquele momento do loop. Logo, é preciso implementar uma função que verifique se um ponto pertence a um segmento.
O trecho de código que eu adicionei à biblioteca de geometria foi:
// Retorna true se q está no segmento p1-p2bool onSegment(const point& p1, const point& p2, const point& q) { if (min(p1.x, p2.x) <= q.x && q.x <= max(p1.x, p2.x) && min(p1.y, p2.y) <= q.y && q.y <= max(p1.y, p2.y)) return true; else return false;}bool inPolygon(point pt, const vector<point> &p){ if (p.size() < 3) return false; double sum = 0; for (int i=0; i < (int)p.size()-1; ++i) { if (onSegment(p[i],p[i+1], pt)) // verifica se o ponto está na borda { return true; } // true se p[i+1] está a esquerda de pt p[i] if (ccw(pt, p[i], p[i+1])) { sum += angle(p[i], pt, p[i+1]); //left } else { sum -= angle(p[i], pt, p[i+1]); //right } } return fabs( fabs(sum) - 2*M_PI ) < EPS;}