Um detalhe interessante é que nas primeiras horas poucos enviaram soluções mas entre os que enviaram a taxa de acerto era bem alta. Foi realmente um problema para separar os homens dos garotos (e eu fiquei na pré-adolescência).
Para preparar este post baixei algumas soluções dos primeiros colocados e dei uma olhada nas poucas descrições disponíveis na internet (como esta). O terceiro colocado parece ter feito um solução muito elegante em Haskell; infelizmente não entendo nada desta linguagem.
Descrição do Problema
A descrição é relativamente simples: o que se deseja é saber a probabilidade de acertar uma mosca com uma raquete de tenis. A figura abaixo mostra a modelagem a ser adotada. A mosca é o circulo laranja de raio f. A raquete é também circular, com raio externo R. A raquete tem um aro de espessura t. As cordas da raquete são simétricas em relação ao centro, tem raio r (devem ser tratadas como faixas de largura 2r) e estão espaçadas de g. A mosca está dentro da raquete e considera-se que ela foi acertada se encostar no aro ou em alguma das cordas.
A resposta é considerada correta se tiver erro inferior ou igual a 10e-6.Minha Tentativa de Solução
Duas coisas me fizeram entrar em pânico: números em ponto flutuante e as curvas onde as cordas se juntam ao aro. Embora fosse claro que uma solução era calcular a área coberta pelo aro e cordas, eu simplesmente não vi como fazer isto. Nas soluções que examinei, este foi o método mais usado e o que vou implementar adiante.
Tendo ignorado o método mais fácil, imaginei duas possibilidades:
- usar o Método de Monte Carlo: supondo que eu conseguiria determinar se uma mosca em uma determinada posição seria atingida ou não, gerar aleatoreamente um número muito grande de posições e contar a porcentagem de acertos. Embora correta, não senti firmeza suficiente para ir nesta linha. Pelo menos uma das soluções que eu examinei parece ter usado este método.
- fazer uma integração manual: já que eu não sabia calcular a área, pensei em somar distâncias: variar o y pouco a pouco e para cada y verificar qual o tamanho da parte livre e da parte ocupada pelo aro+cordas. Foi o que tentei fazer e me enrosquei todo. Algumas soluções corretas fizeram algo parecido, porém usaram retângulos ao invés de retas e calcularam uma aproximação para as áreas.
Uma Alternativa Geometricamente Correta
A figura abaixo mostra o primeiro quadrante, vamos adotar o centro da circunferência da raquete como o centro das nossas coordenadas. Reparar que na parte central o espaço livre entre as cordas são quadrados de lado g. A área livre para a mosca em cada um destes quadrados é (g - 2*f)^2 (obviamente, se g for menor que 2*f a mosca não tem por onde escapar).
O nosso problema são os quadrados que são cortados pelo aro da raquete (para sermos mais precisos, pelo aro mais a margem necessária para a mosca passar). A figura abaixo mostra as quatro possibilidades:
A figura mostra também como podemos calcular a área de um deles: temos um "gomo" (setor) do qual precisamos descontar a área de dois triângulos. De forma análoga os demais casos podem ser calculados a partir da área de gomo, triângulo e retângulo.
A área do gomo é calculada a partir do ângulo, que por sua vez é calculado pelo arco-tangente. A área dos triângulos pode ser calculada diretamente a partir das coordenadas dos seus vértices. Os pontos de intersecção dos quadrados com o aro podem ser facilmente calculados: conhecemos uma das coordenas e os pontos de uma circunferência com centro em (0,0) seguem a relação x^2 + y^2 = R^2.
O cálculo é feito percorrendo um a um os quadrados gerados pelas cordas. Se o quadrado estiver todo dentro do círculo, é só calcular a área do quadrado. Se estiver todo fora, a área de interesse é zero. Se estiver parcialmente dentro, é preciso verificar em qual dos quatro casos ele se encaixa e calcular a área.
O Código
O código abaixo é uma reformatação do código do participante 'klopyrev'.
A primeira coisa necessária é saber se um ponto está dentro ou fora de uma circunferência:
int Inside (double x, double y, double R)
{
return (x*x + y*y) <= R*R;
}
double CoordCirc (double coord, double R)
{
return sqrt (R*R - coord*coord)
}
double TriArea (double x1, double y1, double x2, double y2)
{
return fabs (x1*y2 - x2*y1) / 2.0;
}
double SectorArea (double x1, double y1, double x2, double y2, double R)
{
double ang = fabs (atan2 (y1, x1) - atan2 (y2, x2));
return ang * R * R / 2.0;
}
double SqrArea (double R, double x1, double y1, double s)
{
double yint1, yint2, xint1, xint2;
if(!Inside (x1, y1, R))
return 0; // totaly outside
if(Inside (x1+s, y1+s, R))
return s*s; // totaly inside
if(!Inside (x1, y1+s, R))
{
if(Inside(x1+s, y1, R))
{ // case 1
yint1 = CoordCirc (x1, R);
yint2 = CoordCirc (x1+s, R);
return SectorArea (x1, yint1, x1+s, yint2, R) + (yint2-y1)*s
- TriArea (x1, yint1, x1, yint2)
- TriArea (x1,yint2,x1+s,yint2);
}
else
{ // case 2
yint1 = CoordCirc (x1, R);
xint1 = CoordCirc (y1, R);
return SectorArea (x1, yint1, xint1, y1, R)
- TriArea (xint1, y1, x1, y1)
- TriArea (x1, y1, x1, yint1);
}
}
else
{
if(Inside(x1+s, y1, R))
{ // case 3
xint1 = CoordCirc (y1+s, R);
yint1 = CoordCirc (x1+s, R);
return SectorArea (xint1, y1+s, x1+s, yint1, R) + s*(xint1-x1)
+ (x1+s-xint1)*(yint1-y1)
- TriArea (xint1, y1+s, xint1, yint1)
- TriArea (x1+s, yint1, xint1, yint1);
}
else
{ // case 4
xint1 = CoordCirc (y1+s, R);
xint2 = CoordCirc (y1, R);
return SectorArea (xint1, y1+s, xint2, y1, R) + s*(xint1-x1)
- TriArea (xint1, y1+s, xint1, y1)
- TriArea (xint1, y1, xint2, y1);
}
}
}
Agora é só gerar todos os quadrados no nosso programa principal e comparar a área não livre com a área total:
totalarea = PI*R*R;
hitarea = PI*R*R;
if ((g - 2*f) > 0)
{
double removedArea = 0;
for(i = 0; TRUE; i++)
{
int maxj = -1;
for(j = 0; TRUE; j++)
{
double x1 = (g+2*r)*i + r + f;
double y1 = (g+2*r)*j + r + f;
double a = SqrArea(R-t-f, x1, y1, g-2*f);
if (a == 0)
break;
maxj = j;
removedArea += a;
}
if (maxj == -1)
break;
}
removedArea *= 4;
hitarea -= removedArea;
}
printf ("Case #%d: %f\n", iCase, hitarea/totalarea);
Nenhum comentário:
Postar um comentário