#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct point
{
ld x,y;
int ind = -1;
bool operator<(const point& other) const
{
if(ind > 0) return ind < other.ind;
if(x == 0 && y == 0) return 0;
if(other.x == 0 && other.y == 0) return 1;
if(x == other.x && y == other.y) return 0;
int d1 = y > 0;
int d2 = other.y > 0;
if(d1 != d2)
{
if(y <= 0) return 0;
return 1;
}
if(x*other.y-other.x*y != 0)
{
return x*other.y-other.x*y < 0;
}
else
{
int d1 = y > 0;
int d2 = other.y > 0;
if(d1 != d2)
{
if(y > 0) return 0;
return 1;
}
if(y == other.y && y == 0)
{
return x>other.x;
}
return (abs(x)+abs(y))>(abs(other.x)+abs(other.y));
}
}
};
bool is180(point p1, point p2)
{
return p1.x*p2.y-p2.x*p1.y>0;
}
map<ld,int> lines[2];
set<ld> dif_lines;
int lines_cnt;
int cnt_180;
pair<ld,ld> points[100001];
int cur = 1;
multiset<point> sort_points;
map<pair<ld,ld>,int> point_cnt;
int rel_ind[100001];
void add(ld x, ld y, int c)
{
int type = 0;
if((x == 0 && y <= 0) || x > 0) type = 1;
ld p = round(x/y*1e12);
dif_lines.insert(p);
if(y == 0) p = -1;
lines[type][p]++;
if(lines[type][p] == 1 && lines[type^1][p] >= 1) lines_cnt++;
point_cnt[{x,y}]++;
if(siz(sort_points) == 0)
{
sort_points.insert({x,y,c});
cnt_180++;
}
else
{
auto nxt = sort_points.upper_bound({x,y,c});
point nx;
if(nxt == sort_points.end())
{
nx = *(sort_points.begin());
}
else
{
nx = *nxt;
}
point pv;
if(nxt != sort_points.begin())
{
nxt--;
pv = *nxt;
}
else
{
pv = *(--sort_points.end());
}
point p = {x,y,c};
if(is180(pv,nx) || siz(sort_points) == 1) cnt_180--;
if(is180(pv,p)) cnt_180++;
if(is180(p,nx)) cnt_180++;
sort_points.insert(p);
}
}
void del(ld x, ld y, int c)
{
int type = 0;
if((x == 0 && y <= 0) || x > 0) type = 1;
ld p = round(x/y*1e12);
if(y == 0) p = -1;
if(lines[type][p] == 1 && lines[type^1][p] >= 1) lines_cnt--;
lines[type][p]--;
if(lines[type][p]+lines[type^1][p] == 0) dif_lines.erase(p);
point_cnt[{x,y}]--;
if(siz(sort_points) == 1)
{
sort_points.erase(sort_points.find({x,y,c}));
cnt_180--;
}
else
{
sort_points.erase(sort_points.find({x,y,c}));
auto nxt = sort_points.upper_bound({x,y,c});
point nx;
if(nxt == sort_points.end())
{
nx = *(sort_points.begin());
}
else
{
nx = *nxt;
}
point pv;
if(nxt != sort_points.begin())
{
nxt--;
pv = *nxt;
}
else
{
pv = *(--sort_points.end());
}
point p = {x,y,c};
if(is180(pv,nx) || siz(sort_points) == 1) cnt_180++;
if(is180(pv,p)) cnt_180--;
if(is180(p,nx)) cnt_180--;
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
ld x1,y1,z1;
cin >> x1 >> y1 >> z1;
int cyc = 0;
while(z1 == 0)
{
cyc++;
swap(z1,y1);
swap(y1,x1);
}
bool is_zero = (z1 == 0);
if(x1 != 0 || y1 != 0)
{
ll g = __gcd((ll)x1,(ll)y1);
x1 /= g;
y1 /= g;
z1 /= g;
}
if(!is_zero)
{
x1 /= z1;
y1 /= z1;
}
int n;
cin >> n;
vector<pair<char,int>> opers;
rep(i,n)
{
char z;
cin >> z;
if(z == 'A')
{
ld x,y,z;
cin >> x >> y >> z;
opers.pb({'A',-1});
rep(i,cyc)
{
swap(z,y);
swap(y,x);
}
if(x != 0 && y != 0)
{
ll g = __gcd((ll)x,(ll)y);
x /= g;
y /= g;
z /= g;
}
if(z != 0)
{
x /= z;
y /= z;
x -= x1;
y -= y1;
}
add(x,y,-cur);
points[cur++] = {x,y};
}
else
{
int x;
cin >> x;
opers.pb({'R',x});
}
}
int p = 1;
forall(it,sort_points)
{
rel_ind[-it.ind] = p++;
}
lines_cnt = 0;
cnt_180 = 0;
dif_lines = {};
rep(d,2) lines[d] = {};
point_cnt = {};
sort_points = {};
cur = 1;
forall(it,opers)
{
if(it.ff == 'A')
{
add(points[cur].ff,points[cur].ss,rel_ind[cur]);
cur++;
}
else
{
del(points[it.ss].ff,points[it.ss].ss,rel_ind[it.ss]);
}
if(point_cnt[{0,0}]) cout << "1\n";
else if(lines_cnt > 0) cout << "2\n";
else if(cnt_180 == 0 && siz(sort_points) > 2 && siz(dif_lines) > 1) cout << "3\n";
else 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... |