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