Submission #887227

#	Time	Username	Problem	Language	Result	Execution time	Memory
887227		heavylightdecomp	Tri (CEOI09_tri)	C++14	30 / 100	83 ms	9412 KiB

tri

#include<bits/stdc++.h>
using namespace std;
#define ld long double
#define int long long
#define EPS (ld)(1e-14)
#define vt vector
int K,M;
struct line {
    ld m;
    ld c;
    line() {}
    line(ld a, ld b) {
        m = a;
        c = b;
    }
};
ld interx(line a, line b) {
    ld res = (ld)(b.c - a.c) / (ld)(a.m - b.m);
    return res;
}
struct {
    vt<line> emb;
    vt<pair<ld, line>> sta;
    void push(line g) {
        emb.push_back(g);
    }
    bool bye(pair<ld, line> g, line h) {
        ld cut = g.first;
        if(interx(g.second, h) <= cut) {
            return true;
        }
        return false;
    }
    void solve() {
        sort(begin(emb), end(emb), [](line a, line b) {return a.m > b.m; });
        for(line curr: emb) {
            while(sta.size() and bye(sta.back(), curr)) {
                sta.pop_back();
            }
            ld ccut = -1e10;
            if(sta.size()) {
                ccut = interx(curr, sta.back().second);
            }
            if(ccut <= 1e18) sta.push_back({ccut, curr});
        }
        // cerr << "Yep done\n";
    }
    bool query(ld x, ld maxy) {
        auto lb = lower_bound(begin(sta), end(sta), x, 
            [](pair<ld, line> a, ld q) { 
                return a.first < q;
            }
        ); //BUG: Upper bound was so much more weird compared to lower bound
        //Otherwise code was good, trust your code.
        assert(lb != begin(sta));
        lb = prev(lb);
        line now = lb->second;
        return (now.m * (ld)x + now.c) <= (ld)maxy;
    }
} cht;
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> K >> M;
    for(int i = 1; i <= K; i++) {
        int xp, yp;
        cin >> xp >> yp;
        cht.push(line(-xp, yp));
    }
    cht.solve();
    for(int g = 1; g <= M; g++) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        ld m = (ld)(y2 - y1) / (ld)(x2 - x1);
        ld b = -m * (ld)x1 + (ld)y1;
        // cerr << m << ' ' << b << '\n';
        bool res = cht.query(m, b);
        if(res) {
            cout << "Y\n";
        } else {
            cout << "N\n";
        }
    }

}

• Subtask 1: 30 / 100