526互联

Codeforces 103446A - Strange Functions（凸包）

发布时间 2023-04-25 15:26:02作者: tzc_wk

首先，根据 \(\arctan\) 函数的性质，一个函数在 \(x\) 处的取值是所有 \(n\) 个函数中最小的，当且仅当 \(|k_i\sec(x-a_i)|\) 是所有 \(n\) 个函数中最小的。

和差角公式把 \(\sec\) 拆开得到 \(|\dfrac{k_i}{\cos(x)\cos(a_i)+\sin(x)\sin(a_i)}|\)，取个倒数变成 \(|\dfrac{\cos(x)\cos(a_i)+\sin(x)\sin(a_i)}{k_i}|\)。记 \(y_i=\dfrac{\cos(a_i)}{k_i},x_i=\dfrac{\sin(a_i)}{k_i}\)，那么这个式子变成 \(|\cos(x)y_i+\sin(x)x_i|\)，相当于我们要对每个函数求是否存在 \(x\) 使得这个式子的值是所有函数中最大的。

令所有式子除以 \(\cos(x)\)，变成 \(|y_i+\tan(x)x_i|\)（注：由于外面有个绝对值符号，因此不用 \(\cos(x)\) 的符号带来不等号方向的变化，且当 \(\cos(x)=0\) 时，可视作 \(\cos(x)=\epsilon\) 的情况），这可以视作用斜率为任意实数的直线去截 \((-x_i,y_i)\) 的点，得到斜率绝对值的最大值。根据绝对值的性质，我们对每个函数建两个点 \((x_i,-y_i)\) 和 \((-x_i,y_i)\)，只要这两个点中任意一个取到截距的最大值，这个函数在 \(x\) 处就是所有函数中的最小值。

这下就好办了，直接对 \(2n\) 个点求一遍凸包，凸包上的点就是答案。

const int MAXN=1e5;
const ld EPS=1e-12;
int n,k[MAXN+5];ld a[MAXN+5];
struct point{
	double x,y;int id;
	point(){x=y=0;}
	point(ld _x,ld _y){x=_x;y=_y;}
	friend point operator +(const point &X,const point &Y){return point(X.x+Y.x,X.y+Y.y);}
	friend point operator -(const point &X,const point &Y){return point(X.x-Y.x,X.y-Y.y);}
	friend ld operator ^(const point &X,const point &Y){return X.x*Y.x+X.y*Y.y;}
	friend ld operator |(const point &X,const point &Y){return X.x*Y.y-X.y*Y.x;}
	friend bool operator <(const point &X,const point &Y){return mp(X.x,X.y)<mp(Y.x,Y.y);}
}p[MAXN*2+5];
int ok[MAXN+5];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%Lf",&k[i],&a[i]);
		p[i].y=cos(a[i])/k[i]*1e8;p[i].x=-sin(a[i])/k[i]*1e8;p[i].id=i;
		p[i+n]=p[i];p[i+n].x=-p[i+n].x;p[i+n].y=-p[i+n].y;
	}
	static int stk[MAXN*2+5];int tp=0;
	sort(p+1,p+2*n+1);
	for(int i=1;i<=2*n;i++){
		while(tp>=2&&((p[i]-p[stk[tp]])|(p[stk[tp-1]]-p[stk[tp]]))<=EPS)tp--;
		stk[++tp]=i;
	}
	for(int i=1;i<=tp;i++)ok[p[stk[i]].id]=1;
	for(int i=1;i<=n;i++)printf("%d",ok[i]);printf("\n");
	return 0;
}