「BalticOI 2020」混合物

「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|Pin S})，此时

情况1即(T)包含原点

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

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

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

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

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

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

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

能包含即(x+2pi-y<pi)

#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");
		} 
	}
}