Submission #1263166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263166		patgra	Mixture (BOI20_mixture)	C++20	0 / 100	1 ms	324 KiB

Mixture

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

struct frac {
    ll num, den;
};
bool operator== (frac a, frac b) {
    return a.num * b.den == a.den * b.num;
}
bool operator< (frac a, frac b) {
    if(a.den * b.den > 0) return a.num * b.den < a.den * b.num;
    return a.num * b.den > a.den * b.num;
}
frac operator+ (frac a, frac b) {
    frac c = { a.num * b.den + b.num * a.den, a.den * b.den };
    auto g = gcd(c.num, c.den);
    c.num /= g, c.den /= g;
    if(c.den < 0) c.num *= -1, c.den *= -1;
    return c;
}
frac operator* (frac a, frac b) {
    frac c = { a.num * b.num, a.den * b.den };
    auto g = gcd(c.num, c.den);
    c.num /= g, c.den /= g;
    if(c.den < 0) c.num *= -1, c.den *= -1;
    return c;
}
frac operator/ (frac a, frac b) {
    frac c = { a.den, a.num };
    return c * b;
}
frac operator- (frac a, frac b) {
    a.num *= -1;
    return a + b;
}

struct pt {
    frac x, y;
};
bool operator< (pt a, pt b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

frac X, Y, Z;
vector<pt> pts;
multiset<pt> ms;

frac crossProd(pt x, pt y, pt rel) {
    pt xRel = {x.x - rel.x, x.y - rel.y};
    pt yRel = {y.x - rel.x, y.y - rel.y};
    return xRel.x * yRel.y - xRel.y * yRel.x;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> X.num >> Y.num >> Z.num;
    X.den = Y.den = Z.den = max(1ll, Z.num);
    int q;
    cin >> q;
    rep(i, 0, q) {
        char c;
        cin >> c;
        if(c == 'A') {
            int a, b, d;
            cin >> a >> b >> d;
            if(d == 0) {
                pts.pb({frac{a, 1} + X, frac{b, 1} + Y});
                ms.insert({frac{a, 1} + X, frac{b, 1} + Y});
            }
            else {
                pts.pb({frac{a, d}, frac{b, d}});
                ms.insert({frac{a, d}, frac{b, d}});
            }
        }
        else {
            int x;
            cin >> x;
            x--;
            ms.erase(ms.find(pts[x]));
        }
        bool g = 0;
        repIn2(x, y, ms) if(x == X && y == Y) g = 1;
        if(g) { cout << "1\n"; continue; }
        rep(it, ms.begin(), prev(ms.end())) {
            auto [x1, y1] = *it;
            rep(it2, next(it), ms.end()) {
                auto [x2, y2] = *it2;
                if(x1 == X) {
                    if(x2 != X) continue;
                    if((y1 < Y && Y < y2) || (y2 < Y && Y < y1)) g = 1;
                    continue;
                }
                if(x2 == X) continue;
                auto a1 = (y1 - Y) / (x1 - X);
                auto b1 = Y - X * a1;
                auto a2 = (y2 - Y) / (x2 - X);
                auto b2 = Y - X * a2;
                if(a1 == a2 && b1 == b2 && ((x1 < X && X < x2) || (x2 < X && X < x1))) g = 1;
            }
        }
        if(g) { cout << "2\n"; continue; }
        if(ms.size() > 2) rep(it1, ms.begin(), prev(prev(ms.end()))) rep(it2, next(it1), prev(ms.end())) rep(it3, next(it2), ms.end()) {
            auto cp1 = crossProd({X, Y}, *it1, *it3);
            auto cp2 = crossProd({X, Y}, *it2, *it3);
            if((cp1 < frac{0, 1} && frac{0, 1} < cp2) || (frac{0, 1} < cp1 && cp2 < frac{0, 1})) g = 1;
        }
        if(g) { cout << "3\n"; continue; }
        cout << "0\n";
    }
}

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