自动搬运

查看原文

来自洛谷，原作者为

	BJpers2 **

搬运于2025-08-24 21:45:31，当前版本为作者最后更新于2019-03-06 16:35:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道很好的计算几何题，结合了CDQ分治的思想，而且也不需要很毒瘤的前置知识（比如三维凸包，半平面交之类）。

为了表述方便，我们强制令$B \geq 0$

首先根据套路，遇到这种“只有插入，动态询问”的题目，往往可以往CDQ分治上面去想。

• 一个栅栏是有用的，当且仅当把它之前的所有点带入$Ax+By-C$中去计算，所得值的符号全部相同。又等价于最大，最小值同号。最大值在”以它为斜率的直线在上凸包上的切点”处取到(因为$B \geq 0$),特别地，当$B=0$,在凸包最右端取到。而最小值则相反。

下面只考虑在一次分治中如何转移最大值。

1. 构建上凸包。
2. 对所有直线按照斜率递减排序，竖线强制放在最后，实现上可以把每条非竖直线赋一个指向$x$轴正方向的方向向量，按后面$\times$前面$\leq 0$为基准排序,并令竖线方向指向下，就可以不用特判竖线了。
3. 此后类似于旋转卡壳，将斜率在$(slope(i-1,i),slope(i,i+1)]$中的所有直线的答案更新，在凸包两端的情况特殊注意。

最小值同理，注意几乎所有符号都要取反，且竖线要放左边。

最后判同号时千万别偷懒写$mx[i] \times mi[i]>0$ ,这样做稳爆$long$ $long$,我就因为这拍了半天一直没拍出来，写成$mx[i]<0 || mi[i]>0$就好了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=200200,M=200200;
const ll INF=4e18;
int n,m,cp,cl,r;
ll mx[M],mi[M];
struct vec{
	ll  x,y;
	vec(){}
	vec(ll  a,ll  b){x=a;y=b;}
	vec operator + (vec a){return vec(x+a.x,y+a.y);} 
	vec operator - (vec a){return vec(x-a.x,y-a.y);}
	ll  operator ^ (vec a){return x*a.y-y*a.x;} 
}p[N],h[N],di[M];
struct lin{vec d;int i;}L[M];
struct qry{int o;ll x,y,z;}q[M];
void upd(int i,ll x,ll y){
	ll va=x*q[i].x+y*q[i].y;
	mx[i]=max(mx[i],va);
	mi[i]=min(mi[i],va);
}
bool cmp(vec a,vec b){return a.x==b.x?a.y<b.y:a.x<b.x;}
bool cmp1(lin a,lin b){return (a.d^b.d)>0;}
bool cmp2(lin a,lin b){return (a.d^b.d)<0;}
void sol(int l,int r){
	if(l==r) return;
	int md=(l+r)>>1;
	sol(l,md),sol(md+1,r);cp=cl=0;
	FOR(i,l,  md) if(q[i].o==1) p[++cp]=vec(q[i].x,q[i].y);
	FOR(i,md+1,r) if(q[i].o==2) L[++cl]=(lin){di[i],i};
	if(!(cp*cl)) return; 
	sort(p+1,p+cp+1,cmp);
	h[r=1]=p[1];
	FOR(i,2,cp){
		while(1<r && ((h[r]-h[r-1])^(p[i]-h[r]))<=0) r--;
		h[++r]=p[i];
	} 
	sort(L+1,L+cl+1,cmp1);
	int j=1;
	FOR(i,1,r){
		for(;(i+1>r || (L[j].d^(h[i+1]-h[i]))>=0) && j<=cl;j++) 
			upd(L[j].i,h[i].x,h[i].y);
	}//下凸包 
	
	h[r=1]=p[1];
	FOR(i,2,cp){
		while(1<r && ((h[r]-h[r-1])^(p[i]-h[r]))>=0) r--;
		h[++r]=p[i];
	} 
	sort(L+1,L+cl+1,cmp2);
	j=1;
	FOR(i,1,r){
		for(;(i+1>r || (L[j].d^(h[i+1]-h[i]))<=0) && j<=cl;j++) 
			upd(L[j].i,h[i].x,h[i].y);
	}//上凸包 
} 
int main(){
	scanf("%d%d",&n,&m);m+=n;
	FOR(i,1,n) q[i].o=1,scanf("%lld%lld",&q[i].x,&q[i].y);
	FOR(i,n+1,m){
		scanf("%d",&q[i].o);
		if(q[i].o==1) scanf("%lld%lld",&q[i].x,&q[i].y);
		if(q[i].o==2){
			scanf("%lld%lld%lld",&q[i].x,&q[i].y,&q[i].z);
			if(q[i].y<0) q[i].x*=-1,q[i].y*=-1,q[i].z*=-1; 
			if(q[i].y==0 && q[i].x<0) q[i].x*=-1,q[i].z*=-1;
			di[i]=vec(q[i].y,-q[i].x); 
			mx[i]=-INF;mi[i]=INF;
		}
	}
	sol(1,m);
	FOR(i,n+1,m)if(q[i].o==2) 
		mx[i]-q[i].z<0 || mi[i]-q[i].z>0?puts("YES"):puts("NO");
}