[Codeforces 1028C] Rectangles

[Codeforces 1028C] Rectangles - 1600

문제 설명 : 

n개의 직사각형의 좌표가 주어진다. n개의 직사각형중에서 최소 (n-1)개의 직사각형의 교집합의 좌표를 구하면 된다.

풀이 : 

최소 (n-1)개의 직사각형의 교집합을 구해야 한다. 이는 다른 말로 표현하면 포함하지 않을 단 1개의 직사각형을 고르면 된다는 뜻이다. n개의 직사각형을 모두 살펴보면서 현재 보는 직사각형을 포함하지 않으면 나머지 (n-1)개의 직사각형들은 교집합을 가질 수 있는지 확인하면 된다. 확인하는 연산은 단 O(1)만에 가능하다. 전처리로 1~i까지의 직사각형의 교집합을 저장하는 pref[]배열, (i+1)~n까지 직사각형의 교집합을 저장하는 suf[]배열을 만들어놓고 1~(i-1)범위의 교집합( = pref[i-1] )과 (i+1)~n범위의 교집합( = suf[i+1] )이 서로 교집합이 있는지 살펴보면 된다. 두 직사각형의 교집합 판별 여부는 예전의 reference로 작성한 적이 있고 아래 코드의 83줄에 자세히 나와있다.

주의할 점 : 

원래는 x1<x2, y1<y2가 만족되어야만 유효한 직사각형 좌표라고 할 수 있는데 두 직사각형간에 교집합이 없으면 x1>x2, y1>y2 형태로 저장된다. 이렇게 저장되면 다른 직사각형과의 교집합을 구할 때도 계속 이런 형태로 저장된다.

배운 점 : 

처음에 풀 때는 포함시킬 (n-1)개의 직사각형에 포커스를 맞췄는데, 반대로 생각해서 포함하지 않을 1개의 직사각형만 고려하면 쉽게 풀 수 있다. 그리고 전처리로 pref,suf배열을 이용하면 O(1)만에 구할 수도 있다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct Rec{
    int x1,y1,x2,y2;
 
    Rec(){}
    Rec(int _x1,int _y1,int _x2,int _y2){
        x1=_x1,y1=_y1,x2=_x2,y2=_y2;
    }
 
    // const bool operator<(const S &o) const{
    //     return a<o.a;
    // }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 140009;
const int INF=1<<30;
Rec arr[SIZE],pref[SIZE],suf[SIZE];
 
int main(){
    int n;  scanf("%d",&n);
 
    for(int i=1 ; i<=n ; i++){
        int a,b,c,d;        scanf("%d %d %d %d",&a,&b,&c,&d);
        arr[i]=Rec(a,b,c,d);
    }
 
    pref[0]=Rec(-INF,-INF,INF,INF);
    suf[n+1]=Rec(-INF,-INF,INF,INF);
    pref[1]=arr[1]; suf[n]=arr[n];
 
    for(int i=2 ; i<=n ; i++){
        int x1=arr[i].x1,x2=arr[i].x2,y1=arr[i].y1,y2=arr[i].y2;
        int a1=pref[i-1].x1,a2=pref[i-1].x2,b1=pref[i-1].y1,b2=pref[i-1].y2;
        pref[i].x1=max(x1,a1),
        pref[i].x2=min(x2,a2),
        pref[i].y1=max(y1,b1),
        pref[i].y2=min(y2,b2);
    }
    for(int i=n-1 ; i ; i--){
        int x1=arr[i].x1,x2=arr[i].x2,y1=arr[i].y1,y2=arr[i].y2;
        int a1=suf[i+1].x1,a2=suf[i+1].x2,b1=suf[i+1].y1,b2=suf[i+1].y2;
        suf[i].x1=max(x1,a1),
        suf[i].x2=min(x2,a2),
        suf[i].y1=max(y1,b1),
        suf[i].y2=min(y2,b2);
    }
 
    for(int i=1 ; i<=n ; i++){
        int x1=pref[i-1].x1,x2=pref[i-1].x2,y1=pref[i-1].y1,y2=pref[i-1].y2;
        int a1=suf[i+1].x1,a2=suf[i+1].x2,b1=suf[i+1].y1,b2=suf[i+1].y2;
 
        if(max(x1,a1)<=min(x2,a2) && max(y1,b1)<=min(y2,b2)){
            printf("%d %d\n",max(x1,a1),max(y1,b1));
            return 0;
        }
    }
    assert(0);
}