#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 ll norm(ll v) {
if(abs(v) > kInf)
v = v / abs(v) * kInf;
return v;
}
inline void simplif() {
x = norm(x);
y = norm(y);
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 y / x;
}
pair<ll, frac> id() {
return {cadran(), y / x};
}
pair<ll, frac> opus_redus() {
ll cad = (cadran() + 1) % 4 + 1;
frac tg = y / x;
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
