自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:23:02，当前版本为作者最后更新于2021-07-15 21:20:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

几何 + DS神题。

开始看非常没有思路，但是根据样例我们可以猜到答案一定很小，事实上答案 $\le 3$。

我们不妨先考虑二维的情况，如果我们只有两种调料如何处理。

我们用二元组 $(P,Q)$ 描述一个瓶子，不难发现我们只关心这个比值 $\frac{P}{Q}$ 。而最终我们需要调出的也只需要一个比值。

那么这个比值可以看成数轴上的一个点，显然两个瓶子对应两个点 $A,B$，我们可以调出线段 $AB$ 上对应的任意比值。感性理解一下，如果只用一个瓶子，就是线段端点，再加入另一个瓶子能使得比例偏移。

那么对于三元组 $(X,Y,Z)$ ，我们也只关心比值 $(\dfrac{X}{X+Y+Z},\dfrac{Y}{X+Y+Z})$，现在我们一个瓶子看成平面直角坐标系中的一个点。

那么对于两个瓶子，显然只能调出对应两点线段上的比值。

现在加入第三个瓶子，也就是在这条线段取一个点，再与第三个点连线。不难发现这条连线是动态的，且扫过的面积恰好是以三个点为顶点三角形。

归纳一下，对于 $N$ 个点，可以取到的比值就是 $N$ 点对应凸包里面的比值。

因此答案 $\le 3$。

如果有瓶子与初始点重合，那么答案为 $1$。

如果有两个瓶子的连线经过初始点，那么答案为 $2$。

如果初始点在凸包中，那么答案为 $3$ 。

否则答案为 $0$。

但是朴素维护凸包和连线，和朴素的 $\mathcal{O}(N^4)$ ，没有什么区别。

由于我们只关心瓶子与初始点的位置，所以我们以初始点为端点进行极角排序。

那么经过初始点的连线，意味着存在两个角相差为 $\pi$。

如果初始点在凸包中，意味着大小相邻的两个角相差 $\le \pi$。

我们直接用平衡树维护角度即可，注意精度问题。时间复杂度 $\mathcal{O}(N\log N)$。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int a[N], b[N], c[N], idx, n, s0, s1, s2;
typedef long double db;
db st, ed;
const db pi = acos(-1.0), eps = 1e-15;
struct cmp{bool operator ()(const db &x, const db &y)const{return x + eps < y;}};
multiset<db, cmp>s;
db calc(db x, db y){
	db cur = atan2(x, y);
	if(cur < 0)cur += pi + pi;
	return cur;
}
inline db rev(db ang){
	if(ang > pi)return ang - pi;
	return ang + pi;
}
void ins(int i){
	int sum = a[i] + b[i] + c[i];
	db x = (db)a[i] / sum, y = (db)b[i] / sum;
	if(fabs(x - st) <= eps && fabs(y - ed) <= eps)s0++;
	else {
		db ang = calc(x - st, y - ed);
		if(s.find(ang) == s.end() && s.find(rev(ang)) != s.end())s1++;
		s.insert(ang); 
	}
}
void del(int i){
	int sum = a[i] + b[i] + c[i];
	db x = (db)a[i] / sum, y = (db)b[i] / sum;
	if(fabs(x - st) <= eps && fabs(y - ed) <= eps)s0--;
	else {
		db ang = calc(x - st, y - ed);
		s.erase(s.find(ang));
		if(s.find(ang) == s.end() && s.find(rev(ang)) != s.end())s1--; 
	}
}
int main(){
	scanf("%d%d%d", &a[0], &b[0], &c[0]);
	st = (db)a[0] / (a[0] + b[0] + c[0]), ed = (db)b[0] / (a[0] + b[0] + c[0]);
	scanf("%d", &n);
	char op[2];int x;
	rep(i, 1, n){
		scanf("%s", op);
		if('A' == *op)++idx, scanf("%d%d%d", &a[idx], &b[idx], &c[idx]), ins(idx);
		else scanf("%d", &x), del(x);
		if(s0)puts("1");else if(s1)puts("2");else if(s.size() < 3)puts("0");
		else if((*s.rbegin() - *s.begin()) < pi)puts("0");
		else if((*s.lower_bound(pi) - *(--s.upper_bound(pi))) > pi)puts("0");
		else puts("3");
	}
	return 0;
}