Submission #221221

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
221221	2020-04-09T17:15:29 Z	Gareth618	Tri (CEOI09_tri)	C++14	100 / 100	785 ms	29468 KB

tri

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

struct Point {
    int x, y;
    static int64_t ccw(const Point& a, const Point& b, const Point& c) {
        return 1LL * (a.x - b.x) * (b.y - c.y) - 1LL * (b.x - c.x) * (a.y - b.y);
    }
    inline bool operator<(const Point& p) const {
        return 1LL * y * p.x - 1LL * x * p.y < 0;
    }
};

vector<Point> convexHull(vector<Point>& pts) {
    vector<Point> st;
    st.push_back(pts[0]);
    st.push_back(pts[1]);
    for (int i = 2; i < (int) pts.size(); i++) {
        while (st.size() > 1 && Point::ccw(st[st.size() - 2], st[st.size() - 1], pts[i]) >= 0)
            st.pop_back();
        st.push_back(pts[i]);
    }
    return st;
}

bool below(vector<Point>& hull, Point a, Point b) {
    int lo = 0, hi = hull.size() - 1;
    while (hi - lo > 4) {
        int m1 = (lo + hi) / 2;
        int m2 = (lo + hi) / 2 + 1;
        if (Point::ccw(a, hull[m1], b) > Point::ccw(a, hull[m2], b))
            lo = m1;
        else
            hi = m2;
    }
    int64_t ans = 1e18;
    for (int i = lo; i <= hi; i++)
        ans = min(ans, Point::ccw(a, hull[i], b));
    return ans < 0;
}

class SegmTree {
  private:
    int n;
    vector<Point> pts;
    vector<vector<Point>> tree;

    void build(int node, int left, int right) {
        if (left == right) {
            tree[node].push_back(pts[left]);
            return;
        }
        int mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1, mid + 1, right);
        tree[node].resize(tree[2 * node].size() + tree[2 * node + 1].size());
        merge(
            tree[2 * node].begin(), tree[2 * node].end(),
            tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
            tree[node].begin()
        );
        tree[node] = convexHull(tree[node]);
    }

    bool query(int node, int left, int right, int qLeft, int qRight, Point a, Point b) {
        if (left == qLeft && right == qRight)
            return below(tree[node], a, b);
        int mid = (left + right) / 2;
        if (qRight <= mid)
            return query(2 * node, left, mid, qLeft, qRight, a, b);
        if (qLeft > mid)
            return query(2 * node + 1, mid + 1, right, qLeft, qRight, a, b);
        return query(2 * node, left, mid, qLeft, mid, a, b)
            || query(2 * node + 1, mid + 1, right, mid + 1, qRight, a, b);
    }

  public:
    SegmTree(vector<Point>& arr) :
        n(arr.size()), pts(arr), tree(4 * n) {
            sort(pts.begin(), pts.end());
            build(1, 0, n - 1);
        }

    bool query(Point a, Point b) {
        int lower = lower_bound(pts.begin(), pts.end(), a) - pts.begin();
        int upper = upper_bound(pts.begin(), pts.end(), b) - pts.begin() - 1;
        if (lower > upper)
            return 0;
        return query(1, 0, n - 1, lower, upper, a, b);
    }
};

int main() {
    int n, q; cin >> n >> q;
    vector<Point> pts(n);
    for (int i = 0; i < n; i++)
        cin >> pts[i].x >> pts[i].y;
    SegmTree tree(pts);

    for (int i = 0; i < q; i++) {
        Point a, b; cin >> a.x >> a.y >> b.x >> b.y;
        if (b < a) swap(a, b);
        cout << (tree.query(a, b) ? "Y\n" : "N\n");
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	512 KB	Output is correct
2	Correct	10 ms	640 KB	Output is correct
3	Correct	156 ms	7160 KB	Output is correct
4	Correct	282 ms	15152 KB	Output is correct
5	Correct	560 ms	29468 KB	Output is correct
6	Correct	542 ms	19192 KB	Output is correct
7	Correct	725 ms	24580 KB	Output is correct
8	Correct	633 ms	22520 KB	Output is correct
9	Correct	687 ms	24964 KB	Output is correct
10	Correct	785 ms	27100 KB	Output is correct