Vôlei Marciano - Huxley 643

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-p2
bool 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;
}