백준 14751번 Leftmost Segment

문제 요약

직선이 N개 주어진다. 그리고 쿼리로 x값이 주어진다. 직선들 중에서 x에서 최솟값을 갖는 직선을 출력해야 한다.

직선은 최대 10만개이고 쿼리도 최대 10만개이다.

풀이

문제 자체에서 주어지는 x와 y를 뒤집어서 생각하자. 나는 직선의 식을 뽑는 데에 그게 편했다. 쿼리가 y값인 거보다는 x값인게 편하다.

어떤 방식으로 보든 상관없다. 중요한 것은 직선이 N개 있고 최솟값을 갖는 직선을 찾는 데에 나이브 하게 구하면 $O(N)$이다.

그러나 Convex Hull Trick이라고 불리는 테크닉을 이용하면 쿼리가 $O(logN)$으로 해결이 가능하다. DP 최적화에 주로 사용되긴 하지만 사실 이 테크닉 자체가 이 문제의 상황을 해결하는 방식이다.

정수만으로 연산들을 처리가 가능하지만 그냥 실수를 써도 통과하는 거 같다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const ld EPS = 1e-7;
struct Line {
    ld m, b, x;
    int idx;
    Line() {};
    Line(ld _m, ld _b, ld _x, int _idx) : m(_m), b(_b), x(_x), idx(_idx) {};
    bool operator<(Line& rhs) {
        if (abs(m - rhs.m) < EPS) return b < rhs.b;
        return m > rhs.m;
    }
};

ld minX, maxX;
int N, M;
vector<Line> lines;
vector<pair<ld, int>> queries;
vector<Line> cht;
int ptr;

ld intersect(Line& a, Line& b) {
    return (b.b - a.b) / (a.m - b.m);
}

void addLine(Line& a) {
    if (cht.empty()) {
        cht.push_back(a);
        return;
    }
    while (!cht.empty()) {
        Line top = cht.back();
        if (abs(top.m - a.m) < EPS && top.b < a.b) return;
        if (abs(top.m - a.m) < EPS) cht.pop_back();
        else {
            ld x = intersect(top, a);
            if (x <= top.x) cht.pop_back();
            else break;
        }
    }
    if (cht.empty()) cht.push_back(a);
    else {
        a.x = intersect(cht.back(), a);
        cht.push_back(a);
    }
    if (ptr >= cht.size()) ptr = cht.size() - 1;
    return;
}

int query(ld x) {
    while (ptr < cht.size() - 1 && cht[ptr + 1].x < x + EPS) ++ptr;
    return cht[ptr].idx;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> maxX >> minX;
    cin >> N;
    ld dx = maxX - minX;
    for (int i = 0; i < N; ++i) {
        ld upY, lowY;
        cin >> upY >> lowY;
        ld dy = upY - lowY;
        ld m = dy / dx;
        ld b = lowY - m * minX;
        lines.push_back(Line(m, b, minX, i + 1));
    }
    cin >> M;
    for (int i = 0; i < M; ++i) {
        ld x; cin >> x;
        queries.push_back(make_pair(x, i));
    }
    sort(lines.begin(), lines.end());
    sort(queries.begin(), queries.end());
    vector<int> ans(M);
    for (int i = 0; i < N; ++i) addLine(lines[i]);
    for (int i = 0; i < M; ++i) ans[queries[i].second] = query(queries[i].first);
    for (int i = 0; i < M; ++i) cout << ans[i] << '\n';
    return 0;
}