Praça do Retângulo

praca.cpp

#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;
}