HackerRank Geometry – Geometry Queries

Challenge: Geometry Queries

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464814878

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/geometry-queries/problem

Cerință

There are N lines. Each line has an index between 1 and N. The slope of each line is negative, i.e. it goes from upper-left to lower-right.

There are Q queries. Each of them is in the format `L R x y`, and you should output whether there is any line with index between L and R and the point (x, y) is under it. If there is, then the answer is `YES`, otherwise `NO`.

As you know, any line splits an infinite plane into two regions. The point (x,y) is under the line if that point is at the same region with point (-∞, -∞). If the point lies on the line it does not count.

Input Format
The first line contains N, the number of lines. The following N lines each contains two integers m and n that describes the line mx + n = y.

The next line contains Q, the number of queries. Each subsequent line contains 4 integers L, R, x, y.

Output Format
For each query, output one line containing either `YES` or `NO`.

Constraints
1 ≤ N ≤ 10^5 (Number of lines)
1 ≤ Q ≤ 10^5 (Number of queries)
-10^9 ≤ x ≤ 10^9
-10^9 ≤ y ≤ 10^9
-10^9 ≤ m < 0
-10^9 ≤ n ≤ 10^9
1 ≤ L ≤ R ≤ N

Sample Input

2
-1 3
-2 -4
3
1 2 0 0
1 1 0 0
2 2 0 0

Sample Output

YES
YES
NO

Explanation
The image shows the two lines of the sample input.

<a href="http://hizliresim.com/JEYqEQ">

</a>

_{Time Limits: C/C++ 1 sec, Java/C# 2 sec, other languages follow standard TL given in [Environment](https://hackerrank.com/environment)}

Cod sursă

#include <bits/stdc++.h>
using namespace std;

struct Line {
    long long m, b; // y = m*x + b
};

static inline __int128 eval128(const Line& l, long long x) {
    return (__int128)l.m * x + l.b;
}

// Given sorted by slope increasing and unique slope, build upper hull.
static vector<Line> buildHull(const vector<Line>& lines) {
    vector<Line> hull;
    hull.reserve(lines.size());
    auto bad = [&](const Line& a, const Line& b, const Line& c) -> bool {
        // x_inter(a,b) >= x_inter(b,c)
        // (a.b - b.b)/(b.m-a.m) >= (b.b - c.b)/(c.m-b.m)
        // denominators > 0 (strictly increasing slopes)
        __int128 left = (__int128)(a.b - b.b) * (c.m - b.m);
        __int128 right = (__int128)(b.b - c.b) * (b.m - a.m);
        return left >= right;
    };

    for (const Line& ln : lines) {
        while (hull.size() >= 2 && bad(hull[hull.size() - 2], hull[hull.size() - 1], ln)) {
            hull.pop_back();
        }
        hull.push_back(ln);
    }
    return hull;
}

// Merge two slope-sorted hull vectors, deduplicate same slope by higher intercept.
static vector<Line> mergeBySlope(const vector<Line>& A, const vector<Line>& B) {
    vector<Line> tmp;
    tmp.reserve(A.size() + B.size());
    size_t i = 0, j = 0;
    while (i < A.size() || j < B.size()) {
        Line pick;
        if (j == B.size() || (i < A.size() && A[i].m < B[j].m)) {
            pick = A[i++];
        } else if (i == A.size() || B[j].m < A[i].m) {
            pick = B[j++];
        } else {
            // equal slope, keep bigger intercept
            pick = (A[i].b >= B[j].b) ? A[i] : B[j];
            ++i;
            ++j;
        }
        if (!tmp.empty() && tmp.back().m == pick.m) {
            if (pick.b > tmp.back().b) tmp.back().b = pick.b;
        } else {
            tmp.push_back(pick);
        }
    }
    return tmp;
}

static __int128 queryHull(const vector<Line>& hull, long long x) {
    int l = 0, r = (int)hull.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (eval128(hull[mid], x) <= eval128(hull[mid + 1], x)) l = mid + 1;
        else r = mid;
    }
    return eval128(hull[l], x);
}

int n;
vector<Line> arr;
vector<vector<Line>> seg;

void build(int idx, int l, int r) {
    if (l == r) {
        seg[idx] = {arr[l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(idx << 1, l, mid);
    build(idx << 1 | 1, mid + 1, r);
    vector<Line> merged = mergeBySlope(seg[idx << 1], seg[idx << 1 | 1]);
    seg[idx] = buildHull(merged);
}

__int128 negInf() {
    return -((__int128)1 << 120);
}

__int128 query(int idx, int l, int r, int ql, int qr, long long x) {
    if (qr < l || r < ql) return negInf();
    if (ql <= l && r <= qr) return queryHull(seg[idx], x);
    int mid = (l + r) >> 1;
    __int128 a = query(idx << 1, l, mid, ql, qr, x);
    __int128 b = query(idx << 1 | 1, mid + 1, r, ql, qr, x);
    return (a > b ? a : b);
}

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

    cin >> n;
    arr.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i].m >> arr[i].b;
    }

    seg.assign(4 * (n + 5), {});
    build(1, 1, n);

    int q;
    cin >> q;
    while (q--) {
        int L, R;
        long long x, y;
        cin >> L >> R >> x >> y;
        __int128 mx = query(1, 1, n, L, R, x);
        if (mx > (__int128)y) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}