「BalticOI 2020」混合物

题目大意：

对于给定的向量$\vec{O}=(x,y,z)$

动态维护一个集合$S=\{(x_i,y_i,z_i)\}$

求出最少用几个$S$中的元素能够 实数正系数 线性组合得到$O$

考虑令$\displaystyle x’=\frac{x} {x+y+z},y’=\frac{y} {x+y+z}$，显然$x,y$能够完成组合，$z$就一定成立

此时，问题转化为了一个平面问题，答案分为几种情况

1.$S$包含$O$，答案显然为1

2.$O$在$S$中两点构成的线段上，显然答案为2

3.$O$被某一个三角形包含，答案为3

4.无解

不妨令$T=\{P-O|P\in S\}$，此时

情况1即$T$包含原点

情况2即$T$中某两点与原点共线且在原点两端

情况3即$S$构成的凸包包含原点

因为只需要判断是否包含，所以其实和凸包并没有关系

考虑不包含的情况，则显然可以用一个 以原点为界的半平面 包住$S$中的所有点

因此可以维护每个点的极角，判断是否可以用半平面完全包含

实现上，完全包含可以认为是$\max-\min<\pi$

或者是半平面跨过极角为$0$的位置，此时令$x,y$分别为$<\pi$最大值，$>\pi$最小值

能包含即$x+2\pi-y<\pi$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
typedef long double db;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=2e5+10,INF=1e9+10;
const db eps=1e-9,PI=acos((db)-1);

int n;
struct Node{
	db x,y;
	Node(){ }
	Node(db x,db y):x(x),y(y){ }
	Node operator - (const Node &t) const { return Node(x-t.x,y-t.y); }
	db angle(){ 
		db t=atan2(y,x);
		if(t<-eps) t+=2*PI;
		return t;
	}
} O,A[N];
Node Read() {
	db a=rd(),b=rd(),c=rd(),s=a+b+c;
	return Node(a/s,b/s);
}

int cnt1,cnt2;
char op[2];
struct cmp{ bool operator () (const db &x,const db &y) const { return x+eps<y; } };
multiset <db,cmp> st;
db Go(db x){
	x+=PI;
	if(x>=2*PI) x-=2*PI;
	return x;
}
void Ins(Node x){
	if(fabs(x.x)<eps && fabs(x.y)<eps) return void(cnt1++);
	db y=x.angle();
	if(st.find(y)==st.end() && st.find(Go(y))!=st.end()) cnt2++;
	st.insert(y);
}

void Del(Node x){
	if(fabs(x.x)<eps && fabs(x.y)<eps) return void(cnt1--);
	db y=x.angle();
	st.erase(st.find(y));
	if(st.find(y)==st.end() && st.find(Go(y))!=st.end()) cnt2--;
}

int main(){
	O=Read();
	rep(_,1,rd()) {
		scanf("%s",op);
		if(*op=='A') Ins(A[++n]=(Read()-O));
		else Del(A[rd()]);
		if(cnt1) puts("1");
		else if(cnt2) puts("2");
		else {
			int f=1;
			if(st.empty()) f=0;
			else {
				if(*st.rbegin()-*st.begin()<PI+eps) f=0;
				else {
					auto y=st.upper_bound(PI),x=y; x--;
					if(*x+2*PI-*y<PI+eps) f=0;
				} 
			}
			puts(f?"3":"0");
		} 
	}
}