백준14636 Money for Nothing

작성일 | In

문제 링크

  • http://icpc.me/14636

문제 출처

  • 2017 ACM-ICPC World Finals D번

사용 알고리즘

  • DnC Opt

시간복잡도

  • $O(\min(N, M) \log \max(N, M))$

풀이


이런 식으로 빨간색 점 m개와 파란색 점 n개가 주어졌을 때

  1. 각 변이 좌표축과 평행하고
  2. 왼쪽 아래 점의 색깔이 빨간색이며
  3. 오른쪽 위 점의 색깔이 파란색인

직사각형의 최대 넓이를 구하는 문제입니다.

먼저, 절대 답이 될 수 없는 점들을 제거해줍시다.
임의의 빨간색 점 R보다 왼쪽 아래에 빨간색 점이 존재한다면 R은 절대 답이 될 수 없습니다.
마찬가지고 임의의 파란색 점 B보다 오른쪽 위에 파란색 점이 존재한다면 B는 절대 답이 될 수 없습니다. 이러한 점들을 제거합시다.

위 그림처럼 파란색은 x좌표 오름차순으로, 빨간색은 내림차순으로 번호를 붙여봅시다.
i번 파란점을 사용하면서 넓이가 최대가 되는 빨간점의 번호를 opt[i]라고 하면, opt[i] ≤ opt[i+1]이라는 사실을 관찰할 수 있습니다.

Divide and Conquer Optimization을 이용해 $O(\min(N, M) \log \max(N, M))$에 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, m;
vector<p> _a, _b, a, b;

ll mx;
void f(int s, int e, int l, int r){
    if(s > e) return;
    int m = s + e >> 1;
    ll ret = -4e18, k = s;
    for(int i=l; i<=r; i++){
        ll dx = b[i].x - a[m].x;
        ll dy = b[i].y - a[m].y;
        ll now = (dx < 0 && dy < 0) ? 0 : dx * dy;
        if(now > ret) ret = now, k = i;
    }
    f(s, m-1, l, k); f(m+1, e, k, r);
    mx = max(mx, ret);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m; _a.resize(n), _b.resize(m);
    for(auto &i : _a) cin >> i.x >> i.y; sort(all(_a));
    for(auto &i : _b) cin >> i.x >> i.y; sort(all(_b), greater<p>());
    a.reserve(n), b.reserve(m);
    for(auto i : _a) if(a.empty() || a.back().y > i.y) a.push_back(i);
    for(auto i : _b) if(b.empty() || b.back().y < i.y) b.push_back(i);
    reverse(all(b));
    f(0, a.size()-1, 0, b.size()-1);
    cout << mx;
}