Wifi

A arquitetura do novo museu de ciências é bastante peculiar. O prédio do museu é uma grande sala retangular. Dentro dessa sala existem outras salas retangulares, e dentro delas existem outras salas retangulares, e assim recursivamente, como se fossem caixas dentro de caixas... As paredes das salas não se tocam. Veja um exemplo na parte esquerda da figura, com oito salas.

O diretor quer instalar uma rede wifi que funcione em todo o museu. Para economizar, ele quer comprar o número mínimo possível de antenas. O problema é que, pela forma como foram construídas as paredes das salas, ocorre uma coisa interessante: o sinal wifi é capaz de atravessar as paredes quando vem de dentro para fora, mas estranhamente não atravessa as paredes quando vem de fora para dentro das salas! A figura mostra duas posições possíveis para uma antena, mostrada como um círculo, e a área que o respectivo sinal wifi da antena alcançaria.

Neste problema, dados N retângulos cujos lados são paralelos aos eixos cartesianos, que descrevem as salas do museu, seu programa deve computar o número mínimo possível de antenas que o diretor deve comprar para que a rede wifi funcione em todo o museu