제출 #1263166

#제출 시각아이디문제언어결과실행 시간메모리
1263166patgraMixture (BOI20_mixture)C++20
0 / 100
1 ms324 KiB
#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"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...