Autor da análise: Atol
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3097
Resumo
Dada uma caixa 2D (2 dimensões) de largura W, e uma quantidade N de discos e os
diâmetros dos N discos D[i], 1 <= i <= N, e 1 <= N <= 10, que vão caindo dentro
da caixa na ordem em que foram passados na entrada, o objetivo é determinar
a altura atingida pelo pilha de discos.
Um fato importante é que quando cada disco cai dentro da caixa ele
vai parar em uma posição que minimize a altura do centro do disco (e é dito no enunciado que as
entradas são feitas de forma que a resposta seja única), e o disco sempre se apóia por
apenas dois pontos ao cair na caixa (seja em contato com outro disco, ou com as bordas da caixa).
Caso um disco caia e toque no chão da caixa, então esse disco "rola" para a esquerda o máximo que
conseguir.
Solução
Uma maneira de resolver esse problema é gerar todas as possíveis posições em que o centro do disco pode parar, e são elas:
- apoiado em um outro disco e em uma parede da caixa;
- apoiado em outro disco e no chão da caixa;
- apoiado em outros dois discos;
E então dentre as possíveis posições VÁLIDAS, pegar aquela com a menor altura.
Uma posição válida é tal que o disco não intercepta nenhum outro disco, e também é uma posição que
pode ser atingida pelo disco (tem um desenho no enunciado que mostra um caso de uma posição não
atingível pelo disco, pois não há como ele chegar àquela posição da caixa sem "empurrar" um outro disco, apesar
de não ter intersecção com nenhum outro disco).
Implementação:
Vamos chamar o centro dos K-1 discos que já estão na caixa quando o K-ésimo cai na caixa de (c[i].x, c[i].y),
onde o raio de tal disco é r[i].
O primeiro disco deve ser tratado de forma especial, mas é única a posição em que o primeiro disco cai,
e terá centro (r[1] , r[1]).
A partir daí temos que gerar todos os possíveis pontos em que o K-ésimo disco pode se apoiar, 2 <= K <= N,
e escolher um centro (x,y) válido para o disco, de forma a minimizar y.
Para isso eu implementei 3 funções que tratam cada um dos casos explicados anteriormente.
Uma maneira de encontrar as possíveis posições que estamos procurando é imaginar
que estamos "expandindo" um disco fazendo seu raio aumentar em r[K].
*Caso da parede direita ( para todo i , 1 <= i < K ), gere os pontos (xx,yy) onde o disco pode ir parar.
double dx = W - r[K] - c[i].x;
double rr = r[i] + r[K];
double yy = sqrt( rr * rr - dx * dx) + c[i].y;
double xx = w - r[K];
VERIFICA SE É VÁLIDO!!
*Semelhante para parede esquerda.
*Colisão com chão e um disco i , 1 <= i < K, gere os centros (xx,yy) :
double aux = r[K] + r[i];
aux = aux*aux - ( (r[i]-r[K])*(r[i]-r[K]) );
double xx = c[i].x + sqrt(aux);
double yy = r[K];
VERIFICA SE É VÁLIDO!!
*Caso da colisão com dois outros discos está explicado no enunciado como fazer.
Agora basta implementar a função que verifica se é válido.
Primeiramente precisamos checar se tal centro (xx,yy) com raio r[K] não intercepta algum outro disco, ou parede, ou chão da caixa.
Depois, precisamos verificar se a posição é atingível. Para este caso podemos ver se a "sombra" de nenhum outro disco
incide no disco K. A sombra de um disco S incide no disco K se c[S].y > yy, e c[S].x - r[S] <= xx <= c[S].x + r[S].
Com isso conseguimos colocar o disco K na sua posição correta, fazendo o centro do disco K ser (xx,yy) tal que
o centro seja válido e a altura yy seja mínima.
Discuta o problema
Isso ta certo?!
Olhe no ultimo caso de teste do exemplo, por esse critério, o disco 6 poderia ficar apoiado no disco 2 e na parede da direita, que o centro dele não fica na sombra do disco 3. Mas ele não "passa" pelo disco 3.
é então… não sei… acredito que os testes dos juízes não cobrem todos os casos, ou até mesmo, apesar de acabar colocando um disco no lugar errado não altere a solução.
Eu fiz desse jeito aí, e passou… mas acho que talvez tenha outras condições pra verificar
isso…
Bom, fiz exatamente como descrito acima, e consegui um AC.
Mas tenho quase certeza que isso ta errado. Depois eu vou tentar montar um caso.
Então, minha primeira tentativa usou essencialmente o algoritmo aí em cima, mas tomei WA.
Depois decidi que o floco não deveria cair reto, deveria descer por qualquer caminho, não necessariamente retilíneo, que minimizasse o $y$. Isso faz mais sentido porque em casos como esse
poderia acontecer de se ele for obrigado a cair reto e minimizar o $y$, ele não poder encostar em exatamente duas coisas. (Eu fiz um programinha SDL para visualizar o algoritmo funcionando. Nesse caso, os 3 primeiros flocos formam uma orelha do Mickey e o último tem que cair entre as orelhas e acertar a cabeça dele. Mas ele não pode ir muito para a esquerda nem direita porque senão vai ficar em baixo das orelhas).
Como implementar do meu jeito era chato, eu fiz uma gambiarra. Para cada floco de raio $\rho$ a ser inserido, eu testei não só as posições que você falou mas também, para cada círculo de centro $(x, y)$ e raio $r$ as posições obtidas deixando ele cair das abscissas $x-\rho-r$ e $x+\rho+r$. Aí deu AC.
Esse problema é tão chato (nada contra) que, dado que eu já passei ele, não quero nem olhar mais para ele. Mas realmente acho que a interpretação do enunciado é deixando o floco ter um caminho livre até o local ótimo, i.e., podendo fazer curvas.