Submission #1026301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026301		tvladm2009	Tri (CEOI09_tri)	C++17	100 / 100	180 ms	25116 KiB

tri

#include <bits/stdc++.h>
 
#define F first
#define S second
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
 
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using ll = long long;
 
template<class T> bool ckmin(T&a, const T& b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T&a, const T& b) { return a < b ? a = b, true : false; }
 
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;
 
const int N = 1e5 + 5;
 
struct Point {
    ll x;
    ll y;
    
    bool operator < (Point other) {
        return x * other.y > y * other.x;
    }
};
 
Point p[N];
 
int cmp(Point a, Point b) {
    ll val = a.x * b.y - a.y * b.x;
    if (val == 0) return 0;
    if (val < 0) return 1;
    if (val > 0) return -1;
}
 
ll area(Point a, Point b, Point c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}
 
struct SegTree {
    int n;
    vector<vi> segt;
    bool ans;
    
    void convex_hull(vector<int> &hull, int l, int r) {
        for (int i = l; i <= r; ++i) {
            while (hull.size() >= 2 && area(p[hull[hull.size() - 2]], p[hull[hull.size() - 1]], p[i]) >= 0) hull.pop_back();
            hull.push_back(i);
        }
    }
    
    void build(int v, int tl, int tr) {
        convex_hull(segt[v], tl, tr);
        if (tl == tr) return;
        
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
    }
    
    SegTree(int nn) {
        n = nn;
        segt.resize(4 * n + 1);
        build(1, 1, n);
    }
    
    bool solve(vector<int> &hull, Point a, Point b) {
        int l = 0, r = hull.size() - 1;
        while (l < r) {
            int m = (l + r) / 2;
            ll res1 = area(a, b, p[hull[m]]);
            if (res1 > 0) return 1;
            ll res2 = area(a, b, p[hull[m + 1]]);
            if (res1 > res2) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return area(a, b, p[hull[l]]) > 0;
    }
    
    void query(int v, int tl, int tr, Point a, Point b) {
        if (ans == 1) return;
        if (cmp(b, p[segt[v][0]]) < 0) return;
        if (cmp(a, p[segt[v].back()]) > 0) return;
    
        if (cmp(a, p[segt[v][0]]) <= 0 && cmp(p[segt[v].back()], b) <= 0) {
            ans |= solve(segt[v], a, b);
            return;
        }
        if (tl == tr) return;
        int tm = (tl + tr) / 2;
        query(2 * v, tl, tm, a, b);
        query(2 * v + 1, tm + 1, tr, a, b);
    }
    
    
    bool get(Point a, Point b) {
        ans = 0;
        query(1, 1, n, a, b);
        return ans;
    }
};
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
    sort(p + 1, p + n + 1);
    SegTree t(n);
    
    while (m--) {
        Point a, b;
        cin >> a.x >> a.y >> b.x >> b.y;
        if (cmp(a, b) > 0) swap(a, b);
        cout << (t.get(a, b) ? "Y" : "N") << "\n";
    }
}

Compilation message (stderr)

tri.cpp: In function 'int cmp(Point, Point)':
tri.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
   38 | }
      | ^

• Subtask 1: 100 / 100