\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage[dvips]{graphicx}  

\def\R{\mbox{{\rm I\kern-0.22emR}}} % Set of  the  real numbers
\def\N{{\mbox{{\rm I\kern-0.22emN}}}}
\def\Z{{\rm Z}\!\!{\rm Z}}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}} \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 108C Tel.: 3091 6135}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{-1mm}
\hfill {\footnotesize {\sc Monitor} Bruno Klava}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} klava@linux.ime.usp.br}

\vspace{1cm}

\begin{center}
{\large
MAC323 -- Estruturas de Dados -- 1. sem de 2005
}

\vspace{0.7cm}

{\large  Exercício-Programa 3 -- Entrega: {\bf 2 de junho}}

\vspace{0.5cm}

{\bf Cubebombing }
\end{center}

Dois amigos descobriram um novo jogo de videogame chamado \textbf{Cubebombing}
e logo ficaram viciados nele. O jogo se passa no ano de 2257 e 
é bem bobinho. Alienígenas de uma galáxia
distante estão atacando a federação e sua tarefa é proteger o espaço usando as
tais cubebombs. Os alienígenas são invisíveis a olhos humanos (apesar do
presidente da federação, Mestre Yoda dizer que sente a força deles), 
assim sua busca
é cega. As bombas são muito eficientes em matar os alienígenas, porém a
indústria bélica da federação estava meio enferrujada depois que os Klingows
se renderam, e as bombas têm
diferentes poderes de explosão. A tarefa do jogador é definir uma estratégia de
explosão das bombas que preencha todo o espaço com o menor número de bombas (a
federação enfrenta uma grave crise econômica no século XXIII). A seguir são
dados mais detalhes. 

O espaço da federação a ser defendido pode ser visto como um paralelepípedo de
dimensões $x \times y \times z$ (considere que a origem é o canto inferior,
esquerdo da frente deste poliedro). Quando uma bomba de poder de explosão $d$
explode no ponto $(a, b, c)$ do espaço ocorrem duas coisas: 
\begin{itemize} 
\item tudo dentro do quadrante em que o ponto $(a, b, c)$ se encontra e no
cubo centrado no ponto com lado $2d$ é destruído (os cantos do cubo são $(a-d,
b-d, c-d)$ e $(a+d, b+d, c+d))$;
\item o quadrante em que o ponto se encontra é dividido em até no máximo
6 novos quadrantes,
conforme a figura abaixo. 
\end{itemize} 
Note que se uma bomba explodir no centro de um quadrante em que uma das
dimensões é menor que $2d$ o poder de explosão da bomba não ultrapassa os
limites do quadrante. 

\begin{figure}
\[ \includegraphics*[height=17cm, width=17cm]{ep3f1.eps} \]
\caption{Ao explodir a bomba os quadrantes Q1, $\dots$ Q6 são criados.}
\end{figure}

No jogo o jogador recebe uma a uma as bombas produzidas pela indústria da
federação, verifica qual seu poder bélico e determina em que ponto do espaço a
bomba será explodida. Com a explosão um cubo fica destruído e novos quadrantes
surgem no espaço. 

Sua tarefa neste EP será comparar as estratégias dos dois amigos. O primeiro
deles denomina sua estratégia com o singelo nome de ``Detona tudo''. A
estratégia funciona da seguinte forma. Ele procura entre os 
quadrantes ainda não destruídos tais que a menor de suas dimensões é maior que
$2d$ aquele que tem esta dimensão mínima (se houver empates ele escolhe aquele
em que a segunda e, se persistir o empate, terceira dimensão é menor. Se dois
quadrantes empatarem nas três dimensões escolha o com menor valor na primeira
dimensão, se empatar, na segunda e assim por diante) e explode a bomba no
centro deste quadrante. 
A idéia dele é não desprezar o poder
bélico das bombas e atacar os menores quadrantes primeiro. 

O segundo amigo tem uma estratégia diferente. Ele a chama de ``Atacando pelas
beiradas''. A estratégia consiste de achar o quadrante ainda não destruído
mais próximo da origem, e atacar este quadrante o mais próximo da origem, 
independentemente de desperdiçar uma parte do poder bélico da bomba. Por mais
próximo ele entende o quadrante cuja ponta inferior esquerda e da frente
esteja mais próxima da origem. Mas, note que outras noções de distância
poderiam ser definidas e testadas.

Neste EP vocês deverão fazer vários testes, gerando várias seqüências de
bombas e mostrando em quantos casos ganha cada uma das estratégias. Fique à
vontade para sugerir outras estratégias, combinar as duas, etc. Entregue junto
com seu EP um pequeno relatório com seus testes comparando as duas estratégias
e outras que você vier a implementar.

Em cada uma das simulações, você deverá manter duas árvores rubro-negras. Em
uma delas estarão os quadrantes ainda não destruídos em que a chave da busca é
o tamanho da menor dimensão do quadrante (que será usado pela primeira
estratégia). Na segunda árvore a chave será a distância do quadrante à origem
do espaço (para a segunda estratégia). Implemente as funções de inserção e
remoção em árvores rubro-negras de forma geral para que seja simples usar as
mesmas funções nas duas estruturas (ou em outras que vocês resolvam testar
também). Não será permitido o uso de bibliotecas em que estas estruturas de
dados já estejam disponíveis. 

\end{document}