#include <bits/stdc++.h>
#define difs(x) (x).begin(), (x).end()
#define gc getchar()
#define pc(x) putchar(x)
template<typename T> void scan(T &x){x = 0;bool _=0;T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=char(n%10+48);n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
#ifndef ONLINE_JUDGE
template<typename T>
void pr(T a){std::cerr<<a<<std::endl;}
template<typename T,typename... Args>
void pr(T a, Args... args) {std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args>
void pr(Args... args){}
#endif
using namespace std;
using ld = double;
const int MM = 1e5+5;
const ld pi = acos(-1), eps = 1e-9;
int n, ptr, cnt;
ld x[MM], y[MM];
multiset<ld> angs, difs;
multiset<pair<ld, ld>> pts;
void up(ld f, ld s, bool b){
ld dif = s-f;
pr("dif", dif, b);
if(dif < -eps)
dif += 2*pi;
if(b)
difs.insert(dif);
else
difs.erase(difs.lower_bound(dif-eps));
}
int main(){
#ifdef CLION
freopen("../in", "r", stdin);
#endif
int a, b, c;
scan(a, b, c, n);
x[0] = (ld)a/(a+b+c);
y[0] = (ld)b/(a+b+c);
pr("pi", pi);
pr("init", a, b, c, x[0], y[0]);
for(int t = 0,i; t < n; t++){
if(gc == 'A'){
scan(a, b, c);
i = ++ptr;
x[i] = (ld)a/(a+b+c)-x[0];
y[i] = (ld)b/(a+b+c)-y[0];
pr("ins", a, b, c, x[i], y[i]);
pts.insert({x[i], y[i]});
ld ang = atan2(y[i], x[i]);
pr("ang", ang, y[i], x[i]);
ld opp = ang-pi;
if(opp < -eps){
opp += 2*pi;
}
auto it = angs.lower_bound(opp-eps);
if(it != angs.end() and abs(*it-opp) < eps)
cnt++;
if(size(angs)){
it = angs.lower_bound(ang-eps);
auto pre = it, nx = it;
if(pre == angs.begin())
pre = --angs.end();
else pre--;
if(nx == angs.end())
nx = angs.begin();
if(pre != angs.end()){
//do nothing for the first time
if(size(angs) > 1)
up(*pre, *nx, 0);
up(*pre, ang, 1);
up(ang, *nx, 1);
}
}
angs.insert(ang);
}
else{
scan(i);
pr("del", i);
pts.erase(pts.lower_bound({x[i], y[i]})); // eps?
ld ang = atan2(y[i], x[i]);
pr("ang", ang, y[i], x[i]);
ld opp = ang-pi;
if(opp < -eps)
opp += 2*pi;
auto it = angs.lower_bound(opp-eps);
if(it != angs.end() and abs(*it-opp) < eps)
cnt--;
if(size(angs)){
it = angs.lower_bound(ang-eps);
auto pre = it, nx = it;
if(pre == angs.begin())
pre = --angs.end();
else pre--;
if(nx == angs.end())
nx = angs.begin();
if(pre != angs.end()){
//do nothing for the first time
if(size(angs) > 1)
up(*pre, *nx, 1);
up(*pre, ang, 0);
up(ang, *nx, 0);
}
}
angs.erase(angs.lower_bound(ang-eps)); //eps
}
auto it = pts.lower_bound({0, 0});
pr("f", it->first, it->second);
pr("cnt", cnt);
if(it != pts.end() and abs(it->first) < eps and abs(it->second) < eps){
print(1);
continue;
}
if(cnt){
print(2);
continue;
}
if(size(difs)){
auto itr = --difs.end();
if(itr != difs.end() and *itr < pi){
print(3);
continue;
}
}
print(0);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Execution timed out |
2078 ms |
384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Execution timed out |
2078 ms |
384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Execution timed out |
2078 ms |
384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Execution timed out |
2078 ms |
384 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
