BOJ 14636 - Money for Nothing

문제 링크 : www.acmicpc.net/problem/14636

문제 풀이

호드를 위한 돈. 이 문제를 처음보면 꽤나 직관적이라는 것을 알 수 있다. A그룹에서 숫자 쌍 하나, B그룹에서 숫자 쌍 하나를 꺼내 수 차이의 곱을 최대화 시키는 것이다. 여기서 가장 쉽게 생각할 수 있는 것은 A그룹에서는 숫자쌍이 작을 수록 이득이라는 것과 B그룹에서는 숫자쌍이 클수록 이득이라는 것. 
즉 A그룹에 (1,3),(2,5)가 있으면 (1,3)이 상위호환이기 때문에 (2,5)는 절때 답을 만들 수 없으며, B그룹에서도 똑같은 방법으로 답이 될 수 없는 숫자 쌍 들을 고를 수 있다.

이렇게 숫자 쌍으로 묶고 나니까 좌표평면이 생각나게 되었다. 숫자 쌍을 좌표평면 상의 점으로 대입해서 생각하게 되면, 문제를 좀 더 직관적으로 생각할 수 있다. A그룹의 점을 왼쪽 아래로 하고, B그룹의 점을 오른쪽 위로 하는 가장 큰 직사각형의 넓이를 구하는 문제가 된다. 

물론 모든 점의 쌍에 대해서 모두 해보는 것으로  $O(N)$에 이 문제를 해결할 수 있다. 하지만, 위의 과정을 지난 후, 각 그룹의 점들은 대각선 아래로 배치되어 있고, 이 경우에 우리는 Dnc Opt를 사용할 수 있다. 즉, A 그룹에서 왼쪽 위에 있을수록, 그 점으로 넓이의 최댓값을 이루는 그룹 B의 점도 왼쪽 위에 존재한다는 것이다. 

여기서 임의의 A그룹의 점에 대해서 모든 B그룹의 점이 왼쪽 또는 아래쪽에 있을 수도 있는데, 이러한 경우에 대해서 잘 생각해서 처리를 해주어야 한다. 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
struct poi{
    ll x,y;
};
 
poi brr[1010101];
poi arr[1010101];
 
 
ll acnt,bcnt;
poi a[1010101];
poi b[1010101];
 
bool sf(poi a,poi b){
    if(a.y!=b.y) return a.y>b.y;
    return a.x>b.x;
}
 
bool sf2(poi a,poi b){
    if(a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
 
ll sol(ll bl,ll br,ll al,ll ar){
    ll na=(al+ar)/2;
    ll ans=-1e18;
    ll chk=0;
    if(bl>br) return 0;
    ll mid=(bl+br)/2;
    for(ll i=al;i<=ar;i++){
        ll val=abs(b[mid].x-a[i].x)*abs(b[mid].y-a[i].y);
        if(b[mid].x>a[i].x||b[mid].y>a[i].y) val=-val;
        if(ans<val){
            na=i;
            ans=val;
        }
    }
    return max({ans,sol(bl,mid-1,al,na),sol(mid+1,br,na,ar)});
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%lld %lld",&brr[i].x,&brr[i].y);
    for(i=1;i<=m;i++)
        scanf("%lld %lld",&arr[i].x,&arr[i].y);
 
    sort(arr+1,arr+1+m,sf);
    ll fl=arr[1].x-1;     
    for(i=1;i<=m;i++){
        if(fl<arr[i].x){
            acnt++;
            a[acnt]=arr[i];
            fl=arr[i].x;
        }
    }
 
    sort(brr+1,brr+1+n,sf2);
    fl=brr[1].y+1;     
    for(i=1;i<=n;i++){
        if(fl>brr[i].y){
            bcnt++;
            b[bcnt]=brr[i];
            fl=brr[i].y;
        }
    }
    printf("%lld",sol(1,bcnt,1,acnt));
}