Submission #810239

#	Time	Username	Problem	Language	Result	Execution time	Memory
810239		ymm	Mixture (BOI20_mixture)	C++17	60 / 100	2064 ms	35800 KiB

Mixture

#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 mn, mx;
	set<double> S;
	bool line;
	bool zero;

	void add(pnt A)
	{
		A -= P;
		if (abs(A) < eps) {
			zero = 1;
			return;
		}
		if (!first) {
			F = A;
			first = 1;
		}
		A *= conj(F);
		double theta = arg(A);
		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;
		S.insert(theta);
	}

	int get_ans() {
		if (zero)
			return 1;
		if (line)
			return 2;
		if (first && mx - mn > M_PI - eps)
			return 3;
		return 0;
	}
};

pnt normalize(double x, double y, double z)
{
	double sum = x+y+z;
	x /= sum;
	y /= sum;
	return {x, y};
}

const int N = 100'010;
int n;

namespace seg {
	vector<pnt> t[N*4];
	void add(int l, int r, pnt 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) { add(l, r, P, 0, 0, n); }

	void dfs(obj o0, int i, int b, int e) {
		obj o = o0;
		for (auto P : t[i])
			o.add(P);
		if (e-b == 1) {
			cout << o.get_ans() << '\n';
			return;
		}
		dfs(o, 2*i+1, b, (b+e)/2);
		dfs(o, 2*i+2, (b+e)/2, e);
	}
	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);
	pnt 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);
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40