PKU 3097 - Falling Ice

Autor da análise: AtolAtol

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.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License