Submission #1263222

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

Mixture

// chuj w to ide spac
#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;

#define ld long double

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 = { b.den, b.num };
    return a * c;
}
frac operator- (frac a, frac b) {
    a.num *= -1;
    return a + b;
}

frac X, Y, Z;
struct pt {
    frac x, y;
};

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;
}

ld getAngle(pt x) {
    auto cp = crossProd(x, pt{X + frac{1, 1}, Y}, pt{X, Y});
    ld cd = (ld)cp.num / (ld)cp.den;
    frac dx = X - x.x, dy = Y - x.y;
    frac ds = dx * dx + dy * dy;
    auto sn = cd / sqrt((ld)ds.num / (ld)ds.den);
    auto ang = asinl(sn);
    if(ang < 0) ang += numbers::pi;
    if(x.y < Y) ang += numbers::pi;
    return ang;
}

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

vector<pt> pts;
multiset<pt> ms;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> X.num >> Y.num >> Z.num;
    int divisor = 2;
    if(Z.num == 0) {
        if(Y.num == 0) {
            divisor = 0;
            X.den = Y.den = Z.den = X.num;
            swap(X, Z);
        }
        else {
            divisor = 1;
            X.den = Y.den = Z.den = Y.num;
            swap(Y, Z);
        }
    }
    else X.den = Y.den = Z.den = Z.num;
    pt xd = {X, Y};
    int q;
    cin >> q;
    rep(i, 0, q) {
        char c;
        cin >> c;
        if(c == 'A') {
            int a, b, d;
            cin >> a >> b >> d;
            if(divisor == 1) swap(b, d);
            if(divisor == 0) swap(a, 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; }
        if(ms.size()) 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()) {
            g = 1;
            rep(it, ms.begin(), prev(ms.end())) {
                DC << getAngle(*it) << '\n';
                g = g && getAngle(*next(it)) - getAngle(*it) < numbers::pi;
            }
            DC << getAngle(*prev(ms.end())) << '\n' << eol;
            g = g && getAngle(*ms.begin()) + 2 * numbers::pi - getAngle(*prev(ms.end())) < numbers::pi;
        }
        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