Submission #826684

#TimeUsernameProblemLanguageResultExecution timeMemory
826684QwertyPiMixture (BOI20_mixture)C++14
100 / 100
440 ms22808 KiB
#include <bits/stdc++.h> #define int long long using namespace std; struct V3d{ int x, y, z; void norm(){ int g = __gcd(__gcd(x, y), z); g = abs(g); if(g != 0) x /= g, y /= g, z /= g; } bool operator< (const V3d o) const { if(x != o.x) return x < o.x; if(y != o.y) return y < o.y; if(z != o.z) return z < o.z; return 0; } }; int dot(V3d a, V3d b){ return a.x * b.x + a.y * b.y + a.z * b.z; } __int128_t dot128(V3d a, V3d b){ return (__int128_t) a.x * b.x + (__int128_t) a.y * b.y + (__int128_t) a.z * b.z; } long double triple(V3d a, V3d b, V3d c){ long double r = 0; r += (long double) a.x * b.y * c.z; r += (long double) a.z * b.x * c.y; r += (long double) a.y * b.z * c.x; r -= (long double) a.x * b.z * c.y; r -= (long double) a.y * b.x * c.z; r -= (long double) a.z * b.y * c.x; return r; } V3d operator* (V3d a, int n){ return {a.x * n, a.y * n, a.z * n}; } V3d operator- (V3d a, V3d b){ return {a.x - b.x, a.y - b.y, a.z - b.z}; } V3d operator- (V3d b){ return {-b.x, -b.y, -b.z}; } V3d vds[100011]; int ai = 0; V3d f; long double deg(V3d a, V3d b){ __int128_t p = dot128(a, b); long double q = sqrt((long double) dot128(a, a)) * sqrt((long double) dot128(b, b)); return acos(min(1.0L, (long double) p / q)) * (triple(f, a, b) > 0 ? 1 : -1); } const long double PI = 3.1415926535; struct Angle{ bool init = false; multiset<long double> S; void add(long double d){ S.insert(d); } void rem(long double d){ S.erase(S.find(d)); } bool qry(){ if(!init) return false; if(S.size() < 3) return false; uniform_real_distribution<long double> dist(-PI, PI); random_device rd; long double diff = *S.begin() + PI * 2 - *prev(S.end()); if(diff > PI) return false; auto ptr = S.lower_bound(*S.begin() + PI); if(ptr != S.end() && prev(ptr) == S.begin()) return false; ptr--; if(*next(ptr) - *ptr > PI) return false; return true; } } Solver; struct Handle{ int c1 = 0, c2 = 0; map<V3d, int> cnt; V3d o; void add(V3d a){ a.norm(); if(a.x == 0 && a.y == 0 && a.z == 0) { c1++; return; } if(!Solver.init){ Solver.init = true; o = a; Solver.add(deg(o, a)); }else{ Solver.add(deg(o, a)); } cnt[a]++; if(cnt[a] == 1 && cnt[-a] > 0) c2++; } void rem(V3d a){ a.norm(); if(a.x == 0 && a.y == 0 && a.z == 0) { c1--; return; } Solver.rem(deg(o, a)); cnt[a]--; if(cnt[a] == 0 && cnt[-a] > 0) c2--; } int qry(){ if(c1 > 0) return 1; if(c2 > 0) return 2; if(Solver.qry()) return 3; return 0; } } handle; int32_t main(){ cin.tie(0); cout.tie(0)->sync_with_stdio(false); int x, y, z; cin >> x >> y >> z; f = V3d {x, y, z}; int n; cin >> n; for(int i = 0; i < n; i++){ char c; cin >> c; if(c == 'A'){ int x, y, z; cin >> x >> y >> z; V3d a {x, y, z}; vds[++ai] = a * dot(f, f) - f * dot(a, f); handle.add(vds[ai]); }else{ int x; cin >> x; handle.rem(vds[x]); } cout << handle.qry() << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...