自动搬运

查看原文

来自洛谷，原作者为

	djwj223 .

搬运于2025-08-24 22:35:37，当前版本为作者最后更新于2022-06-18 10:27:55，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

my submission

当然有很多是无效提交，比如说忘开 O2 之类的

讲讲我的心路历程：4 月学模拟退火的时候 A 了 [JSOI2016]炸弹攻击1，看到了这一题，也发现不少人用模拟退火水过了，于是魔改我原题的程序，发现就是草不过，一直 92 ，又 WA 又 T，发现没前途。

那时候就康那些模拟退火过了的程序，发现都是一车面向数据特判。

他们是怎么知道数据的？小编非常疑惑。

于是我弃了这一题。

今天在翻我以前咕咕的题，发现了这一题，是个计算几何题，很有感觉。

于是想怎么做。

之前做过一道 CF 题，大概就是用了角前缀和的思想，发现这题取半径 $=R$ 的时候也适用。

大概就是说有一个选定圆和一车圆（我们暂且把怪物看做半径为 $0$ 的圆），求哪一个在选定圆上的点，被包含在其他圆中的次数最多。

来做这题的人肯定都会，就只要看一个非选定圆对选定圆上的哪段弧有贡献，前缀和一下就好了。

注意，要把自己建筑的圆的贡献设成无穷小，表示不能将其包含在内。

接下来我们考虑证明可能成为最大值的圆心位置的个数是只有严格 $\Theta(n^2m)$ 的。

我们采取这样一种构造：一个点满足存在一个圆心为他的圆，与两个自己的建筑相切，并且也与一个怪物相切（前面已把其定义为圆）。

证明：如果不与怪物相切，那么圆还可以缩小。如果不与两个建筑相切，那么圆还可以放大。

于是圆心个数就被缩成 $2\times 10^5$ 级别的，二分写的稳一点就可以过。

后面还要 $\Theta(n+m)$ 判最大可行直径。

$\text{code}$（部分参考 $\text{Claris}$）：

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define PLDI pair<ld,int>
using namespace std;
const int M=2017;
const ld Eps=1e-9,EEps=1e-4,PI=3.14159265358979323846;
int n,m,ans=1; ll R,d[M][M];
PLDI q[M<<1|1];
struct C{ll x,y,r;}a[M];
struct FC{ld x,y,r;};
inline ll pf(ll x){return x*x;}
inline ld pf(ld x){return x*x;}
inline ld fix(ld x){
	while(x<-Eps) x+=PI*2;
	while(x-PI*2>-Eps) x-=PI*2;
	return max(x,(ld)0.0);
}
inline void solve_for_R(int x){
	int ret=1,cnt=0;
	for(int i=1;i<=n+m;i++) if(i!=x){
		if(d[x][i]>pf(R*2+a[i].r) ||(d[x][i]==pf(R*2+a[i].r) && i<=n)) continue;
		ld A=R,B=R+a[i].r,C=sqrt(d[x][i]); if(i<=n) B-=1e-7;
		ld ang=acos((A*A+d[x][i]-B*B)/(2.0*A*C));
		//余弦定理
		ld st=atan2(a[i].y-a[x].y,a[i].x-a[x].x);
		//本来的当前点到枚举点的方向
		ld l=fix(st-ang),r=fix(st+ang);
		if(fabs(l-r)<Eps) r=l+Eps;
		int v=(i<=n)?-M:1;
		//不能炸到自己的建筑
		if(l>r) ret+=v;
		q[++cnt]=PLDI(l,v),q[++cnt]=PLDI(r,-v);
	}
	ans=max(ans,ret),sort(q+1,q+cnt+1);
	for(int i=1;i<=cnt;i++) ans=max(ans,ret+=q[i].second);
	//类似于前缀和的思路
}
inline void FC_intersection(FC a,FC b,ld& X,ld& Y,int t){
	//求圆交点，t 表示现在求第几个
	ld d2=pf(a.x-b.x)+pf(a.y-b.y),d=sqrt(d2);
	ld l=(d2+pf(a.r)-pf(b.r))/(2.0*d),h=sqrt(max(pf(a.r)-pf(l),(ld)0.0));
	//当前角的正弦和余弦值
	ld vlx=(b.x-a.x)/d*l,vly=(b.y-a.y)/d*l;
	ld vhx=-(b.y-a.y)/d*h,vhy=(b.x-a.x)/d*h;
	if(t==1) vhx*=-1,vhy*=-1;
	X=a.x+vlx+vhx,Y=a.y+vly+vhy;
}
inline void work(ld x,ld y,ld r){
	for(int i=1;i<=n;i++) if(pf(x-a[i].x)+pf(y-a[i].y)-pf(r+a[i].r)<-EEps) return;
	int ret=0; r=pf(r); for(int i=n+1;i<=n+m;i++) if(pf(x-a[i].x)+pf(y-a[i].y)-r<EEps)
		ret++; ans=max(ans,ret);
}
inline void smaller_than_R(int x,int y,int z){
	if(d[x][y]>=pf(R*2+a[x].r+a[y].r)) return;
	for(int nw=0;nw<2;nw++){
		//二分法找出所有有可能是答案的圆心位置
		ld l=(sqrt(d[x][z])-a[x].r)/2.0,r=R,X,Y,mid;
		for(int i=1;i<=100;i++){
			mid=(l+r)/2;
			FC_intersection((FC){a[x].x,a[x].y,a[x].r+mid},(FC){a[z].x,a[z].y,mid},X,Y,nw);
			if(pf(X-a[y].x)+pf(Y-a[y].y)>pf(a[y].r+mid)-EEps) l=mid; else r=mid;
		}
		//这样二分会好些，其他的二分写法会 WA 或者 TLE
		FC_intersection((FC){a[x].x,a[x].y,a[x].r+l},(FC){a[z].x,a[z].y,l},X,Y,nw);
		work(X,Y,l);
	}
}
int main(){
	scanf("%d%d%lld",&n,&m,&R);
	for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].r);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&a[i+n].x,&a[i+n].y);
	for(int i=1;i<=n+m;i++) for(int j=1;j<=n+m;j++)
		d[i][j]=pf(a[i].x-a[j].x)+pf(a[i].y-a[j].y);
	for(int i=n+1;i<=n+m;i++) solve_for_R(i);
	for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++)
		for(int k=n+1;k<=n+m;k++) smaller_than_R(i,j,k);
	printf("%d",ans);
	return 0;
}