C/C++教程

题解[CF575E]Spectator_Riots

本文主要是介绍题解[CF575E]Spectator_Riots,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意

一个球场,可以看作 \(10^5\times10^5\) 的矩形,每个位置都是一个整点。一个位置 \((x,y)\) 位于球场内当且仅当 \(x\in[0,10^5]\and y\in[0,10^5]\) 。

有 \(n\) 个可能捣乱的黑粉,第 \(i\) 个在位置 \((x_i,y_i)\) 上,速度为 \(v_i\),即一秒内可能跑到任意一个距原来位置曼哈顿距离不超过 \(v_i\) 的位置。

前来控制现场的警察有一架无人机,这架无人机能选一秒内黑粉可能到达的三个点,并监控过这三个点的圆内的位置。

求一个选三个点的方案,使得能一秒后监控到的黑粉数的期望值最大,如果有多个期望相同的方案,输出所得圆半径最大的方案。如果还一样,任意一种方案皆可。

思路

看上去很离谱的题(也有可能是博主坐井观天)。我们不妨先多手模几组小数据,找找性质。能发现最优方案貌似都是可以包括到所有可能出现的位置的。大胆地猜测这个结论是正确的,具有普适性。证明?首先可以发现,一个圆包含所有点,当且仅当该圆包含这些点所组成的凸包。充分性显然,必要性考虑反证。如果一个圆包含所有点却不包含凸包,要么是不包含某个凸包顶点,要么是不包含某条边的一部分。第一种情况显然和包含所有点矛盾,而第二种情况与“圆是个凸形”相矛盾。那么问题转化为证明必然有个圆,经过凸包的三个以上顶点且完全覆盖该凸包。考虑一个能包含整个球场的圆,不断缩小,直到与凸包有两个交点。将圆心延两交点连线的中垂线移动,在变得无法完全覆盖凸包前,必然会与凸包的第三个顶点相交。

那么我们现在的问题转化为,怎么构建凸包和在凸包上寻找三个点使得过这三个点的圆半径最大。

关于构建凸包,可以发现最后要用的凸包,等于对于每个黑粉做个凸包,再对这些凸包求凸包的结果。

关于在凸包上求答案的三个点,可以发现三个点越接近共线,圆半径越大。那么我们只要枚举凸包上每相邻三个点求圆的半径即可。

实现

单个黑粉的凸包,画画图就发现可以直接算出来,但是要特判一些超出球场边界的情况。

总凸包,把每个黑粉单独的凸包上的顶点丢进一个数组里,直接用单调栈维护上下凸壳最后,按顺序把凸壳上的点丢进最终算答案的凸包数组即可。

关于圆半径计算,用向量什么的算一算就好,也可以硬解方程推推式子。具体见代码。

代码只保留了核心部分。

int tn,tu,td,tt;
 
struct VECTOR{
	int x,y;
 
	inline bool operator<(const VECTOR u){
		return x!=u.x?x<u.x:y<u.y;
	}
 
	inline VECTOR(){
	}
 
	inline VECTOR(int a,int b){
		x=a,y=b;
	}
 
	inline VECTOR operator-(const VECTOR u){
		return VECTOR(x-u.x,y-u.y);
	}
 
	inline LL operator^(const VECTOR u){		//叉积
		return 1ll*x*u.y-1ll*y*u.x;
	}
 
	inline bool operator==(const VECTOR u){
		return x==u.x&&y==u.y;
	}
 
	inline double Molen(){						//模长
		return sqrt(1.0*x*x+1.0*y*y);
	}
}nd[N*4+10],up[N*4+10],dn[N*4+10],tb[N*4+10];

int main(){
	n=Read();
	for(int i=1;i<=n;++i){						//循环体是对于每个黑粉算其单独的凸包。博主太蠢,只会硬特判。
		int x=Read(),y=Read(),v=Read();
		if(x-v>=0)
			nd[++tn]=VECTOR(x-v,y);
		else if(x>0){
			if(y+v-x<Y)
				nd[++tn]=VECTOR(0,y+v-x);
			if(y-v+x>0)
				nd[++tn]=VECTOR(0,y-v+x);
		}
		if(x+v<=X)
			nd[++tn]=VECTOR(x+v,y);
		else if(x<X){
			if(y+v-(X-x)<Y)
				nd[++tn]=VECTOR(X,y+v-(X-x));
			if(y-v+(X-x)>0)
				nd[++tn]=VECTOR(X,y-v+(X-x));
		}
		if(y-v>=0)
			nd[++tn]=VECTOR(x,y-v);
		else if(y>0){
			if(x+v-y<X)
				nd[++tn]=VECTOR(x+v-y,0);
			if(x-v+y>0)
				nd[++tn]=VECTOR(x-v+y,0);
		}
		if(y+v<=Y)
			nd[++tn]=VECTOR(x,y+v);
		else if(y<Y){
			if(x+v-(Y-y)<X)
				nd[++tn]=VECTOR(x+v-(Y-y),Y);
			if(x-v+(Y-y)>0)
				nd[++tn]=VECTOR(x-v+(Y-y),Y);
		}
		if(X-x+Y-y<=v)
			nd[++tn]=VECTOR(X,Y);
		if(X-x+y<=v)
			nd[++tn]=VECTOR(X,0);
		if(x+y<=v)
			nd[++tn]=VECTOR(0,0);
		if(x+Y-y<=v)
			nd[++tn]=VECTOR(0,Y);
	}
	sort(nd+1,nd+1+tn);
	tn=unique(nd+1,nd+1+tn)-nd-1;
	for(int i=1;i<=tn;++i){
		while(tu>1&&((up[tu]-up[tu-1])^(nd[i]-up[tu]))>=0)
			--tu;
		up[++tu]=nd[i];
		while(td>1&&((dn[td]-dn[td-1])^(nd[i]-dn[td]))<=0)
			--td;
		dn[++td]=nd[i];
	}
	for(int i=1;i<=tu;++i)
		tb[++tt]=up[i];
	for(int i=td-1;i>1;--i)
		tb[++tt]=dn[i];
	for(int i=1;i<=2;++i)
		tb[tt+i]=tb[i];
	double mx=0;
	int ans=0;
	for(int i=1;i<=tt;++i){
		VECTOR a=tb[i+1]-tb[i],b=tb[i+2]-tb[i],c=tb[i+2]-tb[i+1];
		double r=abs(a.Molen()*b.Molen()*c.Molen()/(2*(a^b)));
		if(r>mx)
			mx=r,ans=i;
	}
	return 0;
}
这篇关于题解[CF575E]Spectator_Riots的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!