PKU 2944 - Wild West

Autor da análise: cesargmcesargm

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

Resumo

Estranhos são pontos na forma $(x,y,z)$ ($1 \le x,y,z \le m$).

Dados n estranhos 'vilões', encontrar o número de estranhos 'heróis', ou seja, estranhos $(x^*,y^*,z^*)$ tais que, para cada vilão $(x,y,z)$, vale que:

$x^* > x$ ou $y^* > y$ ou $z^* > z$

Solução

Podemos modelar o problema de forma geométrica. Cada estranho $(x,y,z)$ é representado pelo cubo com pontas em $(x-1,y-1,z-1)$ e $(x,y,z)$. Para cada vilão $(x,y,z)$, os estranhos que não podem vencê-lo (e portanto, não podem ser heróis) são representados pela caixa com pontas em $(0,0,0)$ e $(x,y,z)$. O número de heróis representados por uma figura desse tipo é obviamente o volume da figura.

Então a solução do problema é obtida calculando o volume da união das caixas determinadas por cada vilão (obtendo o número de estranhos que não podem ser heróis) e retirando-o do total ($m^3$).

Para isso, começamos ordenando os pontos em ordem decrescente de uma coordenada (z, por exemplo) e criando um set<pair> para guardar os "pontos de interesse", que são os cantos da figura quando vista de cima (Note que os elementos desse set irão sempre formar uma "escada"). O set começa com os pontos (0,m+1) e (m+1,0) para não precisarmos nos preocupar com os limites.

Processe cada ponto em ordem decrescente de z: Se o ponto (x,y) já está contido na escada (existe (x',y') tal que $x' \ge x$ $y' \ge y$) não é necessário fazer nada. Caso contrário, insira o ponto (x,y) no set, e vá eliminando os pontos com as duas coordenadas menores que o ponto atual e calculando a área adicionada à figura. Se $A$ é a área adicionada (ou seja, a diferença entre a área atual e a área antes de inserir o ponto), some $zA$ ao volume do objeto ($V$).

No final calcule $m^3 - V$. essa é a resposta do problema

Testes

Entrada

Example1

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