Solução Informática - Nível Intermediário - Semana 1

Solução por Pedro Racchetti

Conteúdos utilizados:

Para resolver esse problema, precisamos entender a ideia de intersecção de retângulos. É fácil perceber que um retângulo i faz intersecção com um retângulo j se X1_i \geq X1_j e X1_i \leq X2_j e Y1_i \geq Y1_j  e Y1_i \leq Y2_j . Além disso, nota-se que o ponto descrito no problema tem que estar na intersecção de pelo menos n - 1 retângulos. Podemos portanto, fazer uma função que retorna essa intersecção, caso exista, da seguinte maneira:


retangulo interseccao(retangulo r1, retangulo r2){
int x1 = max(r1.x1, r2.x1);
int x2 = min(r1.x2, r2.x2);
int y1 = max(r1.y1, r2.y1);
int y2 = min(r1.y2, r2.y2);
retangulo resp;
resp.x1 = x1;
resp.x2 = x2;
resp.y1 = y1;
resp.y2 = y2;
return resp;
}

view raw

funcaoretangulo.cpp

hosted with ❤ by GitHub

Sabendo disso, podemos manter um vetor de prefixos das intersecções, de modo que a posição i guarde a intersecção de todos os retângulos j tal que i < j (se tal intersecção não exista, podemos usar um retângulo nulo, que represente que não há intersecção, alterando a função acima), e um vetor análogo aos sufixos. Verificamos então se existe uma intersecção no fim do vetor de prefixos ou uma no início do vetor de sufixos, caso existir, podemos imprimir qualquer ponto dessas intersecções, já que é uma intersecção com todos os retângulos, menos o último ou o primeiro, respectivamente. Caso não exista, iteramos de 1 à n - 2, e verificar se existe a intersecção do prefixo de i - 1 com o sufixo de i + 1, quando existir, imprimimos qualquer ponto dessa intersecção e finalizamos o programa.

Segue o código para melhor entendimento da solução:


#include <bits/stdc++.h>
using namespace std;
const int MAXN = 132694;
int n;
struct retangulo{ // criamos uma struct para representar os retangulos
long long int x1, x2, y1, y2;
bool operator == (retangulo r) const{
if(x1 == r.x1 && x2 == r.x2 && y1 == r.y1 && y2 == r.y2) return true;
return false;
}
};
retangulo v[MAXN]; // o vetor v guarda os retangulos originais
retangulo pref[MAXN], suf[MAXN];
retangulo nullrec;
retangulo interseccao(retangulo r1, retangulo r2){
//verificamos se a intersecção existe
if(r1 == nullrec || r2 == nullrec) return nullrec;
if(r1.x1 > r2.x2 || r2.x1 > r1.x2) return nullrec;
if(r1.y1 > r2.y2 || r2.y1 > r1.y2) return nullrec;
//guardamos as coordenadas da interseccao
int x1 = max(r1.x1, r2.x1);
int x2 = min(r1.x2, r2.x2);
int y1 = max(r1.y1, r2.y1);
int y2 = min(r1.y2, r2.y2);
//retornamos a interseccao
retangulo resp;
resp.x1 = x1;
resp.x2 = x2;
resp.y1 = y1;
resp.y2 = y2;
return resp;
}
int main() {
//deixamos o retangulo nulo com dimensoes inalcancaveis pelas restricoes
nullrec.x1 = 11234567890;
nullrec.x2 = 11234567890;
nullrec.y1 = 11234567890;
nullrec.y2 = 11234567890;
scanf("%d", &n);
for(int i = 0; i < n; i++ ){
scanf("%lld %lld %lld %lld", &v[i].x1, &v[i].y1, &v[i].x2, &v[i].y2);
}
pref[0] = v[0];
//calculamos o prefixo dos retangulos dados
for(int i = 1; i < n; i++)
pref[i] = interseccao(pref[i-1], v[i]);
if(!(pref[n-2] == nullrec)){
printf("%lld %lld\n", pref[n-2].x1, pref[n-2].y1);
return 0;
}
suf[n - 1] = v[n - 1];
//calculamos o sufixo dos retangulos dados
for(int i = n-2; i >= 0; i--)
suf[i] = interseccao(suf[i+1], v[i]);
if(!(suf[1] == nullrec)){
printf("%lld %lld\n", suf[1].x1, suf[1].y1);
return 0;
}
// se chegamos aqui, temos que iterar pelo sufixo e prefixo para achar a resposta
for(int i = 1; i < n-1; i++){
retangulo r = interseccao(pref[i-1], suf[i+1]);
if(!(r == nullrec) ){
printf("%lld %lld\n", r.x1, r.y1);
break;
}
}
return 0;
}

view raw

Rectangle.cpp

hosted with ❤ by GitHub