Rectangle.cpp

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