[백준] 23282번: Line Fighter 2

https://www.acmicpc.net/problem/23282

23282번: Line Fighter 2

---

1. 문제 조건

1) 2차원 평면 상에 1차 함수 $N$개가 주어진다.

2) 기울기 $a$와 $y$ 절편 $b$ 가 주어진다.

3) $x$ 값이 주어잘 때, 직선 $N$개 중에 $x$에 대한 최댓값 혹은 최솟값을 출력한다.

4) 직선의 개수 $N$은 최대 100,000, 쿼리의 개수 $M$은 최대 100,000 이다.

 

2. 문제 접근

단순히 생각하면 쿼리 $x$가 주어질 때마다

직선 $N$개에 모두 대입해서 최댓값 혹은 최솟값을 구하면 된다.

 

그러나 $N$의 최댓값이 100,000, 쿼리 $M$의 최댓값이 100,000 이므로

위 방법으로 단순하게 풀기에는 시간 초과가 날 것이 뻔하다.

따라서 우리는 조금 다른 방법을 생각해야 한다.

 

3. Convex Hull Trick

이 문제는 Convex Hull Trick 의 전형적인 문제다.

CHT 에 대해서는 다른 포스트를 확인하자. (https://kalpaca.tistory.com/67)

 

우선 CHT 를 쉽게 구현하기 위해, 주어진 기울기에 경향성을 만들어주자.

기울기를 오름차순으로 정렬한다.

$y$ 절편은 아무래도 상관 없다.

int N, Q; cin >> N >> Q;
for(int i=0; i<N; i++) {
    ll a, b; cin >> a >> b;
    line[i] = pll(a, b);
}

mergeSort(0, N-1);

 

기울기를 오름차순으로 정렬하면

최댓값과 최솟값을 각각 구하기 위한 CHT 구조체를 만들어야 한다.

그리고 최댓값과 최솟값에 대한 쓸모 있는 직선들을 관리해야 한다.

최댓값 또는 최솟값에 관한 CHT 구조체인지 확인하기 위해, isMax 라는 변수를 두었다.

struct CHT {
    pll deq[MAXN];
    int e;
    bool isMax;	// 최댓값 여부

    void init(bool isMax) {
        e = 0;
        this->isMax = isMax;
    }

    double crossX(pll a, pll b) {
        return 1.0 * (a.b - b.b) / (b.a - a.a);
    }

    void insert(pll line) {
        deq[e] = line;

        if(isMax) {
            while((e > 1) && crossX(deq[e-2], deq[e-1]) >= crossX(deq[e-1], deq[e])) {
                deq[e-1] = deq[e];
                e--;
            }
        }
        else {
            while((e > 1) && crossX(deq[e-2], deq[e-1]) <= crossX(deq[e-1], deq[e])) {
                deq[e-1] = deq[e];
                e--;
            }
        }

        e++;
    }

    double query(double x) {
        int l = 0, r = e - 1;
        while(l < r) {
            int m = (l + r) >> 1;

            if(isMax) {
                if(crossX(deq[m], deq[m+1]) <= x) l = m + 1;
                else                              r = m;
            }
            else {
                if(crossX(deq[m], deq[m+1]) >= x) l = m + 1;
                else                              r = m;
            }
        }

        return deq[l].a * x + deq[l].b;
    }
};

각 쿼리에서 주어지는 $x$ 값은 경향성이 없으므로

이분 탐색으로 최댓값 혹은 최솟값을 찾아야 한다.

 

최댓값을 관리하는지 최솟값을 관리하는지에 따라

쓸모 있는 직선을 구분하기 위한 조건과 이분 탐색의 조건이 달라지므로

잘 생각해서 알고리즘을 구현해야 한다.

 

---

전체 풀이 코드는 다음과 같다.

#include <iostream>
using namespace std;

#define MAXN 100001

#define a first
#define b second

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

pll line[MAXN];
pll temp[MAXN];

bool compare(pll a, pll b) { return a.a < b.a; }

void mergeSort(int start, int end) {
    if(start >= end) return;

    int mid = (start + end) >> 1;
    mergeSort(start, mid);
    mergeSort(mid+1, end);

    int left = start;
    int right = mid + 1;
    int idx = start;

    while(left <= mid && right <= end) {
        temp[idx++] = compare(line[left], line[right]) ?
                      line[left++] : line[right++];
    }

    while(left <= mid) temp[idx++] = line[left++];
    while(right <= end) temp[idx++] = line[right++];

    for(int i=start; i<=end; i++) line[i] = temp[i];
}

struct CHT {
    pll deq[MAXN];
    int e;
    bool isMax;

    void init(bool isMax) {
        e = 0;
        this->isMax = isMax;
    }

    double crossX(pll a, pll b) {
        return 1.0 * (a.b - b.b) / (b.a - a.a);
    }

    void insert(pll line) {
        deq[e] = line;

        if(isMax) {
            while((e > 1) && crossX(deq[e-2], deq[e-1]) >= crossX(deq[e-1], deq[e])) {
                deq[e-1] = deq[e];
                e--;
            }
        }
        else {
            while((e > 1) && crossX(deq[e-2], deq[e-1]) <= crossX(deq[e-1], deq[e])) {
                deq[e-1] = deq[e];
                e--;
            }
        }

        e++;
    }

    double query(double x) {
        int l = 0, r = e - 1;
        while(l < r) {
            int m = (l + r) >> 1;

            if(isMax) {
                if(crossX(deq[m], deq[m+1]) <= x) l = m + 1;
                else                              r = m;
            }
            else {
                if(crossX(deq[m], deq[m+1]) >= x) l = m + 1;
                else                              r = m;
            }
        }

        return deq[l].a * x + deq[l].b;
    }
};

CHT maxCHT, minCHT;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cout.precision(3);
    cout << fixed;

    maxCHT.init(true), minCHT.init(false);

    int N, Q; cin >> N >> Q;
    for(int i=0; i<N; i++) {
        ll a, b; cin >> a >> b;
        line[i] = pll(a, b);
    }

    mergeSort(0, N-1);

    for(int i=0; i<N; i++) {
        maxCHT.insert(line[i]);
        minCHT.insert(line[i]);
    }

    while(Q--) {
        double x; int cmd; cin >> x >> cmd;

        if(cmd == 1) {
            cout << maxCHT.query(x) << '\n';
        }
        else {
            cout << minCHT.query(x) << '\n';
        }
    }

    return 0;
}