Submission #135380

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
135380	2019-07-24T04:31:46 Z	imeimi2000	Tri (CEOI09_tri)	C++17	100 / 100	518 ms	34776 KB

tri

#include <iostream>
#include <algorithm>
#include <vector>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

int cmp(pii a, pii b) {
    llong L = (llong)a.se * b.fs;
    llong R = (llong)a.fs * b.se;
    if (L < R) return -1;
    if (L > R) return 1;
    return 0;
}

pii operator-(pii a, pii b) {
    return pii(a.fs - b.fs, a.se - b.se);
}

int ccw(pii a, pii b) {
    llong ret = (llong)a.fs * b.se - (llong)a.se * b.fs;
    if (ret < 0) return -1;
    if (ret > 0) return 1;
    return 0;
}

int ccw(pii a, pii b, pii c) {
    return ccw(b - a, c - b);
}

int n, q;
pii ps[100000];
vector<pii> low[1 << 18], upp[1 << 18];;

void get_convex_hull(int s, int e, vector<pii> &lo, vector<pii> &up) {
    vector<pii> P;
    for (int i = s; i <= e; ++i) {
        P.push_back(ps[i]);
    }
    sort(P.begin(), P.end());
    for (pii i : P) {
        int sz;
        while ((sz = lo.size()) > 1 && ccw(lo[sz - 2], lo[sz - 1], i) <= 0)
            lo.pop_back();
        while ((sz = up.size()) > 1 && ccw(up[sz - 2], up[sz - 1], i) >= 0)
            up.pop_back();
        lo.push_back(i);
        up.push_back(i);
    }
}

void init(int i, int s, int e) {
    get_convex_hull(s, e, low[i], upp[i]);
    if (s == e) return;
    int m = (s + e) / 2;
    init(i << 1, s, m);
    init(i << 1 | 1, m + 1, e);
}

bool check_lo(vector<pii> &hull, pii lo, pii hi) {
    int s = 0, e = hull.size() - 1;
    if (ccw(lo, hi, hull[s]) > 0) return 1;
    if (ccw(lo, hi, hull[e]) > 0) return 1;
    pii p = hi - lo;
    if (p < pii(0, 0)) p.fs = -p.fs, p.se = -p.se;
    while (s < e) {
        int m = (s + e) / 2;
        if (ccw(p, hull[m + 1] - hull[m]) > 0) e = m;
        else s = m + 1;
    }
    return ccw(lo, hi, hull[s]) > 0;
}

bool check_up(vector<pii> &hull, pii lo, pii hi) {
    int s = 0, e = hull.size() - 1;
    if (ccw(lo, hi, hull[s]) > 0) return 1;
    if (ccw(lo, hi, hull[e]) > 0) return 1;
    pii p = hi - lo;
    if (p < pii(0, 0)) p.fs = -p.fs, p.se = -p.se;
    while (s < e) {
        int m = (s + e) / 2;
        if (ccw(p, hull[m + 1] - hull[m]) < 0) e = m;
        else s = m + 1;
    }
    return ccw(lo, hi, hull[s]) > 0;
}

bool query(int i, int s, int e, int x, int y, pii lo, pii hi) {
    if (e < x || y < s) return 0;
    if (x <= s && e <= y)
        return check_lo(low[i], lo, hi) || check_up(upp[i], lo, hi);
    int m = (s + e) / 2;
    return query(i << 1, s, m, x, y, lo, hi) ||
            query(i << 1 | 1, m + 1, e, x, y, lo, hi);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> ps[i].fs >> ps[i].se;
    }
    sort(ps, ps + n, [&](pii a, pii b) {
        return cmp(a, b) < 0;
    });
    init(1, 0, n - 1);
    while (q--) {
        pii a, b;
        cin >> a.fs >> a.se >> b.fs >> b.se;
        if (cmp(a, b) > 0) swap(a, b);
        int L = lower_bound(ps, ps + n, a, [&](pii a, pii b) {
            return cmp(a, b) < 0;
        }) - ps;
        int R = lower_bound(ps, ps + n, b, [&](pii a, pii b) {
            return cmp(a, b) < 0;
        }) - ps - 1;
        printf(query(1, 0, n - 1, L, R, a, b) ? "Y\n" : "N\n");
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	12792 KB	Output is correct
2	Correct	15 ms	12792 KB	Output is correct
3	Correct	104 ms	17536 KB	Output is correct
4	Correct	179 ms	24072 KB	Output is correct
5	Correct	373 ms	34776 KB	Output is correct
6	Correct	385 ms	25452 KB	Output is correct
7	Correct	518 ms	28464 KB	Output is correct
8	Correct	468 ms	27060 KB	Output is correct
9	Correct	456 ms	28336 KB	Output is correct
10	Correct	492 ms	29764 KB	Output is correct