HackerRank Geometry – Geometry Queries – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

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

Cerinta

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 $(-\infty, -\infty)$. 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 \leq  N \leq  10^5$ (Number of lines)  
$1 \leq  Q \leq  10^5$ (Number of queries)  
$-10^9 \leq  x \leq  10^9$  
$-10^9 \leq  y \leq  10^9$  
$-10^9 \leq  m < 0$  
$-10^9 \leq  n \leq  10^9$  
$1 \leq  L \leq  R \leq  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"><img src="http://i.hizliresim.com/JEYqEQ.png" /></a>

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

Cod sursa

#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;
}

HackerRank Geometry – Geometry Queries