PKU 2382 - Radio Coverage

Autor da análise: gabrielrcpgabrielrcp

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2382

Resumo

Dados as coordenadas do centro e o raio de uma circunferência $(x_0, y_0, R)$. E as coordenadas do centro e raio de N outras circunferências, cujos centros estejam dentro da primeira.
Encontrar um subconjunto das N circunferências 2 a 2 disjunto e cuja área seja máxima. A resposta é a área da primeira circunferência unida com as desse subconjunto.

Solução

Como $N \leq 10$, podemos tentar todas as $2^N$ combinações de circunferências e ver qual tem a maior área. Verificar se duas circunferências $(x_i, y_i, r_i)$ e $(x_j, y_j, r_j)$ se intersectam é só verificar se $(x_i-x_j)^2 + (y_i-y_j)^2 < (r_i + r_j)^2$. Acho que até aqui todo mundo chegou sem problemas.

O problema é calcular a área total. Como as circunferências não se intersectam, basta calcular as intersecções da primeira circunferência com cada uma dela e subtrair da soma das áreas de cada uma individual. Vou dar a fórmula da intersecção, se quiserem ver como deduzi, me procurem (Gabriel) pessoalmente, só consigo explicar desenhando.

Vamos supor que a circunferência original tem centro (0, 0) e raio R, e a que queremos intersectar tem centro nas coordenadas (x, y) e raio r. Vamos denotar por $d = \sqrt {x^2 + y^2}$. Vamos ainda usar os ângulos:

$t1 = \textrm{acos}[ (R^2 + d^2 - r^2) / (2 R d) ]$
$t2 = \textrm{acos}[ (r^2 + d^2 - R^2) / (2 r d)]$

Assim a área da intersecção vai ser dada por:

$R^2 (t1 - \sin(t1)\cos(t1)) + r^2 (t2 - \sin(t2)\cos(t2))$

Desde que a intersecção entre as duas não seja nem nula, nem uma das circunferências inteira, isso é:

$|R - r| <= d <= R + r$

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