| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 810266 |
2023-08-06T07:47:11 Z |
ymm |
Mixture (BOI20_mixture) |
C++17 |
|
6 ms |
9620 KB |
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
using namespace std;
typedef complex<double> pnt;
const double eps = 1e-8;
struct obj {
pnt P;
bool first;
pnt F;
double argF;
double mn, mx;
set<double> S;
bool line;
bool zero;
double add(pnt A, double argA)
{
double theta = argA - argF;
if (theta > M_PI)
theta -= 2*M_PI;
if (theta < -M_PI)
theta += 2*M_PI;
S.insert(theta);
if (abs(A.real()) < eps && abs(A.imag()) < eps) {
zero = 1;
return theta;
}
if (!first) {
F = A;
argF = argA;
first = 1;
}
mn = min(mn, theta);
mx = max(mx, theta);
double theta2 = theta;
if (theta > 0)
theta2 -= M_PI;
else
theta2 += M_PI;
auto it = S.lower_bound(theta2-eps);
if (it != S.end() && *it - theta2 < eps)
line = 1;
return theta;
}
int get_ans() {
if (zero)
return 1;
if (line)
return 2;
if (first && mx - mn > M_PI - eps)
return 3;
return 0;
}
};
struct preprocP {
pnt P;
double a;
};
pnt normalize(double x, double y, double z)
{
double sum = x+y+z;
x /= sum;
y /= sum;
return {x, y};
}
pnt P;
const int N = 100'010;
int n;
namespace seg {
vector<preprocP> t[N*4];
void add(int l, int r, const preprocP &P, int i, int b, int e) {
if (l <= b && e <= r) {
t[i].push_back(P);
return;
}
if (r <= b || e <= l)
return;
add(l, r, P, 2*i+1, b, (b+e)/2);
add(l, r, P, 2*i+2, (b+e)/2, e);
}
void add(int l, int r, pnt P) {
preprocP Q;
Q.P = P-::P;
Q.a = arg(Q.P);
add(l, r, Q, 0, 0, n);
}
void dfs(obj o0, int i, int b, int e) {
set<double> marg;
o0.S.swap(marg);
obj o = o0;
o.S.swap(marg);
vector<double> kooft;
for (auto P : t[i])
kooft.push_back(o.add(P.P, P.a));
if (e-b == 1) {
cout << o.get_ans() << '\n';
} else {
dfs(o, 2*i+1, b, (b+e)/2);
dfs(o, 2*i+2, (b+e)/2, e);
}
o.S.swap(marg);
for (auto x : kooft)
marg.erase(marg.find(x));
o0.S.swap(marg);
}
void dfs(pnt P) {
obj o = {};
o.P = P;
dfs(o, 0, 0, n);
}
}
pnt readp()
{
ll x, y, z;
cin >> x >> y >> z;
return normalize(x, y, z);
}
pnt a[N];
int l[N];
bool rem[N];
int main()
{
cin.tie(0) -> sync_with_stdio(false);
P = readp();
cin >> n;
int cnt = 0;
Loop (i,0,n) {
char c;
cin >> c;
if (c == 'A') {
a[cnt] = readp();
l[cnt] = i;
++cnt;
} else {
int x;
cin >> x;
--x;
seg::add(l[x], i, a[x]);
rem[x] = 1;
}
}
Loop (i,0,cnt) {
if (!rem[i])
seg::add(l[i], n, a[i]);
}
seg::dfs(P);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
