#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |