Submission #559778

#	Time	Username	Problem	Language	Result	Execution time	Memory
559778		RaresFelix	Mixture (BOI20_mixture)	C++17	0 / 100	1 ms	212 KiB

Mixture

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll kInf = numeric_limits<ll>::max() / 10;

struct frac {
    ll x, y;

    inline void simplif() {
        if(x && abs(y / x) >= kInf) x = 0;
        if(y && abs(x / y) >= kInf) {
            x = abs(x), y = abs(y); // sfera riemann
        }
        if(y < 0) {
            y *= -1;
            x *= -1;
        }
        if(!y) return;
        if(!x) {
            y = 1;
            return;
        }
        ll g = abs(__gcd(abs(x), abs(y)));
        x /= g;
        y /= g;
    }

    frac operator + (const frac &rhs) const {
        frac re;
        re.y = y * rhs.y;
        re.x = x * rhs.y + rhs.x * y;
        re.simplif();
        return re;
    }

    frac operator - (const frac &rhs) const {
        frac re;
        re.y = y * rhs.y;
        re.x = x * rhs.y - rhs.x * y;
        re.simplif();
        return re;
    }

    frac operator * (const frac &rhs) const {
        frac re;
        re.x = x * rhs.x;
        re.y = y * rhs.y;
        if(!re.y) {
            assert(0);
            re.x = kInf;
            re.y = 1;
        }
        re.simplif();
        return re;
    }
    ll neg() const {
        return (x < 0) ^ (y < 0);
    }
    frac operator / (const frac &rhs) const {
        frac re;
        //printf("   Il impart pe %lld / %lld la %lld / %lld de semn %lld %lld\n", x, y, rhs.x, rhs.y, neg(), rhs.neg());
        if(!rhs.x) {
            re.x = kInf;
            re.y = 1;
            if(neg() ^ rhs.neg()) re.x *= -1;
            re.simplif();
            return re;
        }
        re.x = x * rhs.y;
        re.y = y * rhs.x;
        re.simplif();
        return re;
    }
    frac() {
        x = y = 1;
    }
    frac(ll a, ll b) {
        x = a, y = b;
        simplif();
    }
    bool operator < (const frac &rhs) const {
        return (x * rhs.y < rhs.x * y);
    }
};

struct pct {
    frac x, y;
    void print(string mes) {
        cout << mes;
        //printf("(%lld / %lld, %lld / %lld)\n", x.x, x.y, y.x, y.y);
    }
    pct() : x(), y() {}
    pct(frac x, frac y) : x(x), y(y) {}
    pct(ll a, ll b, ll c) : x(a, a + b + c), y(b, a + b + c) {}
    ll cadran() {
        x.simplif(), y.simplif();
        if(x.x > 0 && y.x >= 0) return 1;
        else if(x.x <= 0 && y.x > 0) return 2;
        else if(x.x < 0 && y.x <= 0) return 3;
        return 4;
    }
    void operator -= (const pct &rhs) {
        x = x - rhs.x;
        y = y - rhs.y;
        x.simplif();
        y.simplif();
    }
    frac tg() const {
        return x / y;
    }
    pair<ll, frac> id() {
        return {cadran(), x / y};
    }
    pair<ll, frac> opus_redus() {
        ll cad = (cadran() + 1) % 4 + 1;
        frac tg = x / y;
        tg.simplif();
        return {cad, tg};
    }
    bool operator < (const pct &p) const {
        return tg() < p.tg();
    }
    void sim() {
        x.simplif();
        y.simplif();
    }
};

pct read() {
    ll a, b, c;
    cin >> a >> b >> c;
    return pct(a, b, c);
}

pct chef;
ll n; 

ll nr_identice;
using simb = pair<ll, frac>;
ll nr_perechi_opuse;
multiset<frac> Opus[5];

multiset<pct> Ord[5]; ///punctele orientate pe cadrane

ll nr_pct_hull;

void add(pct nou) {
    nou.sim();
    if(!nou.x.x && !nou.y.x) {
        ++nr_identice;
        ///asta nu va ajuta la nimic altceva...
        return;
    }
    auto [cop, fop] = nou.opus_redus();
    //printf("esenta opusului lui va fi %lld tg: %lld / %lld\n", cop, fop.x, fop.y);
    nr_perechi_opuse += Opus[cop].count(fop);
    auto [cc, fc] = nou.id();
    Opus[cc].insert(fc);

    ///pt convex hull
    Ord[cc].insert(nou);
    ++nr_pct_hull;
    //printf("l-am adaugat la lin & individ %lld(%lld / %lld) \n", cc, fc.x, fc.y);
}
void remove(pct nou) {
    nou.sim();
    if(!nou.x.x && !nou.y.x) {
        --nr_identice;
        return;
    }
    auto [cop, fop] = nou.opus_redus();
    //printf("esenta opusului lui va fi %lld tg: %lld / %lld\n", cop, fop.x, fop.y);
    
    nr_perechi_opuse -= Opus[cop].count(fop);
    auto [cc, fc] = nou.id();
    Opus[cc].erase(Opus[cc].find(fc));

    ///pt convex hull
    Ord[cc].erase(Ord[cc].find(nou));
    --nr_pct_hull;
}

bool unghi_mare(pct v, pct u) {
    //imi spune daca de la v la u am mai mult de pi (in sens trig)
    return !(v.y * u.x < v.x * u.y);
}

pair<pct, pct> pct_lim(ll cad) {
    pair<pct, pct> sig180 = make_pair(pct(frac(100, 1), frac(1, 1)), pct(frac(-1, 1), frac(-100, 1)));
    if(cad == 1) {
        if(Ord[4].empty() || Ord[1].empty()) 
            return sig180;
        return {*Ord[4].rbegin(), *Ord[1].begin()};
    }
    if(cad == 2) {
        if(Ord[1].empty() || Ord[3].empty()) 
            return sig180;
        return {*Ord[1].rbegin(), *Ord[3].begin()};
    }
    if(cad == 3) {
        if(Ord[2].empty() || Ord[4].empty()) 
            return sig180;
        return {*Ord[2].rbegin(), *Ord[4].begin()};
    }
    if(cad == 4) {
        if(Ord[3].empty() || Ord[1].empty()) 
            return sig180;
        return {*Ord[3].rbegin(), *Ord[1].begin()};
    }
    assert(0);
}

bool convex_hull() {
    if(nr_pct_hull < 3) return false;
    ///verificam cadran cu cadran daca este ok
    
    for(ll cad = 1; cad <= 4; ++cad) 
        if(Ord[cad].empty()) {
            auto [v, u] = pct_lim(cad);
            if(unghi_mare(v, u)) {
                return 0;
            }
        }
    return 1;
}

ll rez() {
    if(nr_identice) return 1;
    if(nr_perechi_opuse) return 2;
    if(convex_hull()) return 3;
    return 0;
}
vector<pct> E;

int main() {
    chef = read();
    cin >> n;
    for(ll i = 1; i <= n; ++i) {
        char tip;
        cin >> tip;
        if(tip == 'A') {
            pct nou = read();
            nou -= chef;
            E.push_back(nou);
            add(nou);
        } else {
            ll id;
            cin >> id;
            --id;
            remove(E[id]);
        }
        cout << rez() << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 17
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40