Solução por Rogério Júnior
Para ver o problema original, clique aqui.
Para cada ponto iremos olhar todos os pontos anteriores a ele que podem formar um retângulo com ele. Para tal, vamos usar duas pilhas, a pilha , que guarda os pontos com maior que a coordenada de , e a pilha para os pontos com coordenada menor.
Olhando agora cada ponto anterior ao ponto , ordenadamente segundo a coordenada , suponha que o de seja maior que o de . O ponto do topo da pilha não pode ter menor que , pois se isso ocorrer, estaria dentro do retângulo que ele formaria com . Por isso, devemos excluir o topo da pilha enquanto sua coordenada for maior que a de . 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 com valor de maior. De maneira análoga, se tiver menor que , devemos excluir o topo da pilha enquanto seu valor de for menor que o de .
Para cada ponto , os elementos em e em são pontos que podem formar retângulos com e é o ponto mais à direita, logo se repetirmos o algoritmo para cada ponto , adicionando à resposta a soma dos tamanhos de e , não contaremos nenhum retângulo duas vezes.
Segue o código para melhor entendimento:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |