Solução Praça do Retângulo

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

Para cada ponto $P$ iremos olhar todos os pontos anteriores a ele que podem formar um retângulo com ele. Para tal, vamos usar duas pilhas, a pilha $cima$ , que guarda os pontos com $y$ maior que a coordenada $y$ de $P$ , e a pilha $baixo$ para os pontos com coordenada $y$ menor.

Olhando agora cada ponto $Q$ anterior ao ponto $P$ , ordenadamente segundo a coordenada $x$ , suponha que o $y$ de $Q$ seja maior que o de $P$ . O ponto do topo da pilha $cima$ não pode ter $y$ menor que $Q$ , pois se isso ocorrer, $Q$ estaria dentro do retângulo que ele formaria com $P$ . Por isso, devemos excluir o topo da pilha enquanto sua coordenada $Y$ for maior que a de $Q$ . Note que, assim, a pilha se mantêm sempre crescente e por isso só preciso excluir os elementos de seu topo para garantir que, em toda ela, não há elementos anteriores a $Q$ com valor de $y$ maior. De maneira análoga, se $Q$ tiver $y$ menor que $P$ , devemos excluir o topo da pilha $baixo$ enquanto seu valor de $y$ for menor que o de $Q$ .

Para cada ponto $P$ , os elementos em $cima$ e em $baixo$ são pontos que podem formar retângulos com $P$ e $P$ é o ponto mais à direita, logo se repetirmos o algoritmo para cada ponto $P$ , adicionando à resposta a soma dos tamanhos de $cima$ e $baixo$ , não contaremos nenhum retângulo duas vezes.

Segue o código para melhor entendimento:

	#include <cstdio>
	#include <algorithm>
	#include <vector>

	using namespace std;

	#define MAXN 3300
	#define INF 0x3f3f3f3f

	#define PB push_back
	#define X first
	#define Y second

	typedef pair<int,int> ii;

	int n, resp;

	ii pt[MAXN];

	int main(){

	scanf("%d", &n);

	for(int i=1; i<=n; i++) scanf("%d %d", &pt[i].X, &pt[i].Y);

	// ordeno os pontos pela coordenada X
	sort(pt+1, pt+n+1);

	// para cada ponto
	for(int i=1; i<=n; i++){

	int ref=pt[i].Y;

	vector<int> cima, baixo;

	// olho todos os pontos anteriores
	for(int j=1; j<i; j++){

	int y=pt[j].Y;

	// se ele estiver acima do ponto referencial
	if(y>=ref){

	// excluo da pilha cima todos os pontos que estão acima do que estou olhando,
	// pois ele estaria dentro dos retângulos formados por eles
	while(!cima.empty() and cima.back()>y) cima.pop_back();

	// e coloco e novo ponto na pilha cima
	cima.PB(y);
	}

	// se ele estiver abaixo do ponto referencial
	else{

	// excluo, analogamente, todos os pontos abaixo do que estou olhando
	while(!baixo.empty() and baixo.back()<y) baixo.pop_back();

	// e coloco o novo ponto na pilha baixo
	baixo.PB(y);
	}
	}

	// adiciono a soma das quantidades de elementos nas pilhas à resposta
	resp+=(cima.size()+baixo.size());
	}

	// e imprimo o valor da resposta
	printf("%d\n", resp);

	return 0;
	}

view raw

praca.cpp

hosted with ❤ by GitHub