| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 587008 |
2022-07-01T08:07:21 Z |
반딧불(#8396) |
Mixture (BOI20_mixture) |
C++17 |
|
0 ms |
212 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef TEST
typedef long long ll;
#else
typedef __int128 ll;
#endif
struct vector2{
ll x, y;
vector2(){}
vector2(ll x, ll y): x(x), y(y){}
vector2 operator-()const{
return vector2(-x, -y);
}
vector2 operator-(const vector2 &r)const{
return vector2(x-r.x, y-r.y);
}
ll cross(vector2 r)const{
return x*r.y - y*r.x;
}
bool operator<(const vector2 &r)const{
if((make_pair(y, x) > make_pair(ll(0), ll(0))) ^ (make_pair(r.y, r.x) > make_pair(ll(0), ll(0)))){
return make_pair(y, x) > make_pair(ll(0), ll(0));
}
return (vector2(0, 0) - *this).cross(r - *this) < 0;
}
bool operator==(const vector2 &r)const{
return x==r.x && y==r.y;
}
};
ll ccw(vector2 a, vector2 b){
return a.cross(b);
}
ll ccw(vector2 a, vector2 b, vector2 c){
return (b-a).cross(c-a);
}
ll mabs(ll x){
return x>=0?x:-x;
}
vector2 calc(ll A, ll B, ll C, ll x, ll y, ll z){
C += A+B, z += x+y;
A*=z, B*=z, x*=C, y*=C;
x-=A, y-=B;
ll g = mabs(__gcd(x, y));
if(g) x/=g, y/=g;
return vector2(x, y);
}
long long A, B, C;
int n;
vector2 arr[100002];
int arrCnt;
/// ans=1 ���
int oneCnt;
/// ans=2 ���
map<vector2, ll> twoMp;
ll twoCnt;
/// ans=3 ���
map<vector2, int> threeMp;
bool threeCnt; /// 180�� �ʰ��� ������ ���°�?
bool large(vector2 a, vector2 b){
return ccw(a, vector2(0, 0), b) > 0;
}
bool calc3(){
vector2 prv;
if(threeMp.size() <= 2) return false;
for(auto it = threeMp.begin(); it != threeMp.end(); ++it){
if(it == threeMp.begin()){
prv = it->first;
continue;
}
if(ccw(prv, vector2(0, 0), it->first) >= 0) return false;
prv = it->first;
}
if(ccw(prv, vector2(0, 0), threeMp.begin()->first) >= 0) return false;
return true;
}
void addPoint(){
long long x, y, z;
scanf("%lld %lld %lld", &x, &y, &z);
int i = ++arrCnt;
arr[i] = calc(A, B, C, x, y, z);
/// ans=1 update
if(arr[i] == vector2(0, 0)){
oneCnt++;
return;
}
/// ans=2 update
twoMp[arr[i]]++;
twoCnt += twoMp[-arr[i]];
/// ans=3 update
// threeMp[arr[i]]++;
// threeCnt = calc3();
// return;
if((int)threeMp.size() < 2){
threeMp[arr[i]]++;
if((int)threeMp.size() == 2 && twoCnt) threeCnt = 1;
else threeCnt = 0;
return;
}
if(threeMp.find(arr[i]) != threeMp.end() || threeCnt){
threeMp[arr[i]]++;
return;
}
auto it = threeMp.lower_bound(arr[i]);
bool delOrig = 0;
if(it == threeMp.begin()) delOrig = large(threeMp.rbegin()->first, threeMp.begin()->first);
else delOrig = large(prev(it)->first, it->first);
if(delOrig) threeCnt = 1;
threeMp[arr[i]]++;
// for(auto p: threeMp) printf("(%lld, %lld) ", p.first.x, p.first.y);
// puts("");
it = threeMp.lower_bound(arr[i]);
assert(it != threeMp.end());
bool newOrig = 0;
if(it == prev(threeMp.end())) newOrig |= large(it->first, threeMp.begin()->first);
else newOrig |= large(it->first, next(it)->first);
if(it == threeMp.begin()) newOrig |= large(threeMp.rbegin()->first, it->first);
else newOrig |= large(prev(it)->first, it->first);
if(newOrig) threeCnt = 0;
}
void delPoint(){
int i;
scanf("%d", &i);
/// ans=1 update
if(arr[i] == vector2(0, 0)){
oneCnt--;
return;
}
/// ans=2 update
twoCnt -= twoMp[-arr[i]];
twoMp[arr[i]]--;
/// ans=3 update
threeMp[arr[i]]--;
if(!threeMp[arr[i]]) threeMp.erase(arr[i]);
threeCnt = calc3();
return;
if((int)threeMp.size() <= 2){
threeMp[arr[i]]--;
if(!threeMp[arr[i]]) threeMp.erase(arr[i]);
if((int)threeMp.size() == 2 && twoCnt) threeCnt = 1;
else threeCnt = 0;
return;
}
if(threeMp[arr[i]] > 1 || !threeCnt){
threeMp[arr[i]]--;
return;
}
threeMp.erase(arr[i]);
if((int)threeMp.size() == 2 && twoCnt){
threeCnt = 1;
return;
}
auto it = threeMp.lower_bound(arr[i]);
bool newOrig = 0;
if(it == threeMp.begin() || it == threeMp.end()) newOrig = large(threeMp.rbegin()->first, threeMp.begin()->first);
else newOrig = large(prev(it)->first, it->first);
if(newOrig) threeCnt = 0;
}
void print(){
if(oneCnt) puts("1");
else if(twoCnt) puts("2");
else if(threeCnt) puts("3");
else puts("0");
}
int main(){
scanf("%lld %lld %lld %d", &A, &B, &C, &n);
for(int i=1; i<=n; i++){
char c;
scanf(" %c", &c);
if(c=='A') addPoint();
else delPoint();
print();
}
}
Compilation message
Mixture.cpp: In function 'void addPoint()':
Mixture.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%lld %lld %lld", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp: In function 'void delPoint()':
Mixture.cpp:149:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d", &i);
| ~~~~~^~~~~~~~~~
Mixture.cpp: In function 'int main()':
Mixture.cpp:201:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
201 | scanf("%lld %lld %lld %d", &A, &B, &C, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Mixture.cpp:204:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
204 | scanf(" %c", &c);
| ~~~~~^~~~~~~~~~~
Mixture.cpp: In function 'bool calc3()':
Mixture.cpp:21:36: warning: 'prv.vector2::x' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | return vector2(x-r.x, y-r.y);
| ^
Mixture.cpp:82:13: note: 'prv.vector2::x' was declared here
82 | vector2 prv;
| ^~~
Mixture.cpp:21:36: warning: 'prv.vector2::y' may be used uninitialized in this function [-Wmaybe-uninitialized]
21 | return vector2(x-r.x, y-r.y);
| ^
Mixture.cpp:82:13: note: 'prv.vector2::y' was declared here
82 | vector2 prv;
| ^~~
| # |
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 |
0 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 |
0 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 |
0 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 |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
