Submission #1208577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208577		vasfor	Tri (CEOI09_tri)	C++20	10 / 100	627 ms	131072 KiB

tri

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;

const int inf = 1e9;
const ll inf64 = 1e18;

struct output {
    vector<int> res;

    void print() {
        for (auto x : res) cout << (x ? "Y" : "N") << "\n";
    }

    bool operator == (const output& o) const {
        return res == o.res;
    }
};

struct pt {
    ll x = 0;
    ll y = 0;

    pt operator-(const pt& o) const {
        return {x - o.x, y - o.y};
    }

    ll vector_mul(const pt& o) const {
        return 1ll * x * o.y - 1ll * o.x * y;
    }

    bool operator<(const pt& o) const {
        return vector_mul(o) > 0;
    }
};

ll area(pt a, pt b, pt c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}

int cmp2(pt a, pt b){
    ll val=a.x*b.y-b.x*a.y;
    if(val==0)return 0;
    if(val<0)return 1;
    return -1;
}

const int MAXN = 1e5 + 5;

pt p[MAXN];

struct segtree{
    int n;
    vector<vector<int>>seg;
    bool ans;
    void convex_hull(vector<int>&hull,int l,int r){
        for(int i=l;i<=r;++i){
            while(hull.size()>=2 and area(p[hull[hull.size()-2]],p[hull.back()],p[i])>0)
                hull.pop_back();
            hull.push_back(i);
        }
    }
    void build(int v,int l, int r){
        convex_hull(seg[v],l,r);
        if(l==r)return;
        int mid=(l+r)>>1;
        build(v<<1,l,mid);
        build(v<<1|1,mid+1,r);
    }
    segtree(int xd):n(xd){
        seg.resize(n<<2);
        build(1,1,n);
    }
    bool solve(vector<int>&hull,pt a,pt b){
        int l=0,r=hull.size()-1;
        while(l<r){
            int mid=(l+r)>>1;
            ll res1=area(a,b,p[hull[mid]]);
            if(res1>0)return 1;
            ll res2=area(a,b,p[hull[mid+1]]);
            if(res1>res2)r=mid-1;
            else l=mid+1;
        }
        return area(a,b,p[hull[l]])>0;
    }
    void query(int v,int l,int r,pt a,pt b){
        if(ans)return;
        if(cmp2(b,p[l])<0)return;
        if(cmp2(a,p[r])>0)return;
        
        if( cmp2(a,p[l])<=0 and cmp2(p[r],b)<=0  ){
            ans|=solve(seg[v],a,b);
            return;
        }
        
        if(l==r)return;
        int mid=(l+r)>>1;
        query(v<<1,l,mid,a,b);
        query(v<<1|1,mid+1,r,a,b);
    }
    bool get(pt a,pt b){
        ans=0;
        query(1,1,n,a,b);
        return ans;
    }
};

pll intersect_lines(pt L1, pt L2) {
    // f(t) = x + t * y
    // x1 + t * y1 == x2 + t * t2
    // t = (x2 - x1) / (y1 - y2)
    ll u = L2.x - L1.x;
    ll v = L1.y - L2.y;
    if (v < 0) u = -u, v = -v;
    return {u, v};
}

bool cmp(pll p1, pll p2) {
    return __int128(p1.first) * p2.second < __int128(p2.first) * p1.second;
}

struct CHT {
    vector<pt> st;

    CHT() = default;

    CHT(vector<pt> a) {
        sort(a.begin(), a.end(), [&](pt p1, pt p2) {
            if (p1.y != p2.y) return p1.y < p2.y;
            else return p1.x < p2.x;
        });
        for (auto p : a) {
            if (!st.empty() && st.back().y == p.y) {
                st.back().x = p.x;
                continue;
            }
            while ((int) st.size() >= 2) {
                pt L1 = st[(int) st.size() - 2];
                pt L2 = st[(int) st.size() - 1];
                auto x1 = intersect_lines(L1, L2);
                auto x2 = intersect_lines(L2, p);
                if (cmp(x1, x2)) break;
                else st.pop_back();
            }
            st.push_back(p);
        }
    }

    ll get_max(int p, int q) {
        // p * x + q * y -> max
        // p > 0
        // p * (x + (q / p) * y) -> max
        // arg = q / p
        assert(p > 0);
        pll x0 = {q, p};
        int bl = 0, br = (int) st.size(), bm;
        while (br - bl > 1) {
            bm = bl + (br - bl) / 2;
            pll x = intersect_lines(st[bm], st[bm + 1]);
            if (cmp(x0, x)) br = bm;
            else bl = bm;
        }
        ll max_value = -8e18;
        for (int di = -10; di <= 10; ++di) {
            int i = bl + di;
            if (i < 0 || i >= (int) st.size()) continue;
            ll tmp_value = 1ll * p * st[i].x + 1ll * q * st[i].y;
            if (tmp_value > max_value) {
                max_value = tmp_value;
            }
        }
        return max_value;
    }
};

struct RangeTree {
    int n = 0;
    vector<vector<pt>> pts;
    vector<CHT> cht_xy_pos, cht_xy_neg, cht_yx_pos, cht_yx_neg;

    RangeTree(const vector<pt>& a): n(a.size()), pts(4 * n), 
        cht_xy_pos(4 * n), cht_xy_neg(4 * n), cht_yx_pos(4 * n), cht_yx_neg(4 * n)
    {
        build(a, 1, 0, n - 1);
    }

    void build(const vector<pt>& a, int v, int tl, int tr) {
        if (tl == tr) {
            pts[v].push_back(a[tl]);
        } else {
            int tm = tl + (tr - tl) / 2;
            build(a, v << 1, tl, tm);
            build(a, v << 1 | 1, tm + 1, tr);

            {
                pts[v] = pts[v << 1];
                copy(pts[v << 1 | 1].begin(), pts[v << 1 | 1].end(), back_inserter(pts[v]));
            }
        }
        cht_xy_pos[v] = CHT(pts[v]);
        
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
        cht_xy_neg[v] = CHT(pts[v]);
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;

        for (auto& p : pts[v]) swap(p.x, p.y);

        cht_yx_pos[v] = CHT(pts[v]);
        
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
        cht_yx_neg[v] = CHT(pts[v]);
        for (auto& p : pts[v]) p.x = -p.x, p.y = -p.y;
        
        for (auto& p : pts[v]) swap(p.x, p.y);
    }

    ll get_max(int v, int tl, int tr, int l, int r, int p, int q) {
        if (l <= tl && tr <= r) {
            if (p > 0) return cht_xy_pos[v].get_max(p, q);
            else if (p < 0) return cht_xy_neg[v].get_max(-p, -q);
            else {
                if (q > 0) return cht_yx_pos[v].get_max(q, p);
                else {
                    assert(q < 0);
                    return cht_yx_neg[v].get_max(-q, -p);
                }
            }
        } else {
            int tm = tl + (tr - tl) / 2;
            ll res = -5e18;
            if (l <= tm) {
                ll tmp = get_max(v << 1, tl, tm, l, r, p, q);
                if (tmp > res) res = tmp;
            }
            if (r > tm) {
                ll tmp = get_max(v << 1 | 1, tm + 1, tr, l, r, p, q);
                if (tmp > res) res = tmp;
            }
            return res;
        }
    }

    ll get_max(int l, int r, int p, int q) {
        // px + qy -> max
        return get_max(1, 0, n - 1, l, r, p, q);
    }
};

struct input {
    int n, m;
    vector<pt> a;
    vector<pair<pt, pt>> b;

    input() = default;

    void read() {
        cin >> n >> m;
        a.resize(n);
        b.resize(m);
        for (auto& p : a) cin >> p.x >> p.y;
        for (auto& [l, r] : b) {
            cin >> l.x >> l.y >> r.x >> r.y;
        }
    }

    void print() {
        cout << n << " " << m << "\n";
        for (auto p : a) cout << p.x << " " << p.y << "\n";
        for (auto [l, r] : b) {
            cout << l.x << " " << l.y << " " << r.x << " " << r.y << "\n";
        }
    }

    void gen() {
        static mt19937 rnd(42);
        const int MAXN = 500;
        const int MAXX = 5;
        n = rnd() % MAXN + 1;
        m = rnd() % MAXN + 1;
        a.resize(n);
        for (auto& p : a) {
            p.x = rnd() % MAXX + 1;
            p.y = rnd() % MAXX + 1;
        }
        b.resize(m);
        for (auto& [l, r] : b) {
            while (1) {
                l.x = rnd() % (MAXX + 1);
                l.y = rnd() % (MAXX + 1);
                r.x = rnd() % (MAXX + 1);
                r.y = rnd() % (MAXX + 1);
                if (l.vector_mul(r) == 0) continue;
                if (l.x < r.x && l.y <= r.y) continue;
                if (l.x > r.x && l.y >= r.y) continue;
                int ok = 1;
                for (auto p : a) {
                    if (l.vector_mul(p) == 0 || r.vector_mul(p) == 0 || (r - l).vector_mul(p) == 0) {
                        ok = 0;
                        break;
                    }
                }
                if (!ok) continue;
                break;
            }
        }
    }

    void gen_max_test() {

    }

    output fast() {
        sort(a.begin(), a.end(), [&](pt p1, pt p2) {
            return p1.vector_mul(p2) > 0;
        });

        RangeTree rt(a);

        vector<int> res;
        res.reserve(m);

        for (auto [l, r] : b) {
            
            if (l.vector_mul(r) < 0) swap(l, r);
            int ql = 1e9, qr = -1e9;
            if (l.vector_mul(a.back()) > 0) {
                int bl = -1, br = (int) a.size() - 1, bm;
                while (br - bl > 1) {
                    bm = bl + (br - bl) / 2;
                    if (l.vector_mul(a[bm]) > 0) br = bm;
                    else bl = bm;
                }
                ql = br;
            }
            if (a.front().vector_mul(r) > 0) {
                int bl = 0, br = (int) a.size(), bm;
                while (br - bl > 1) {
                    bm = bl + (br - bl) / 2;
                    if (a[bm].vector_mul(r) > 0) bl = bm;
                    else br = bm;
                }
                qr = bl;
            }
            if (ql <= qr) {
                pt v = r - l;
                ll tmp = rt.get_max(ql, qr, -v.y, v.x);
                ll C = v.vector_mul(l);
                res.push_back(tmp > C);
            } else {
                res.push_back(0);
            }
        }

        return output{res};
    }

// #ifdef DEBUG
    output slow() {
        vector<int> res;
        res.reserve(m);
        for (auto [l, r] : b) {
            if (l.vector_mul(r) < 0) swap(l, r);
            int any = 0;
            for (auto p : a) {
                if (l.vector_mul(p) > 0 && p.vector_mul(r) > 0 && (r - l).vector_mul(p - l) > 0) {
                    any = 1;
                    break;
                }
            }
            res.push_back(any);
        }
        return output{res};
    }
// #endif
};

void test_case() {
    input in;
    in.read();
    output res = in.fast();
    res.print();
}

void work() {
    int t = 1;
#ifdef DEBUG
    cin >> t;
#endif
    while (t--)
        test_case();
}

#ifdef DEBUG
void test() {
    for (int t = 1;;t++) {
        input in;
        in.gen();
        input in_fs = in;
        input in_sl = in;
        output fs = in_fs.fast();
        output sl = in_sl.slow();
        if (fs == sl) {
            cout << "OK" << endl;
            fs.print();
            cout << "\n=========" << endl;
        } else {
            cout << "WA " << t << "\n";
            cout << "exp\n";
            sl.print();
            cout << "\n=========\n";
            cout << "fnd\n";
            fs.print();
            cout << "\n=========\n";
            in.print();
            break;
        }
    }
}
#endif

#ifdef DEBUG
void max_test() {
    input in;
    in.gen_max_test();
    input in_fs = in;
    output fs = in_fs.fast();
    fs.print();
}
#endif

signed main() {

#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    work();
//    test();
//    max_test();

    return 0;
}

• Subtask 1: 10 / 100