P8061 题解
djwj223
·
·
题解
my submission
当然有很多是无效提交，比如说忘开 O2 之类的
讲讲我的心路历程：4 月学模拟退火的时候 A 了 [JSOI2016]炸弹攻击1，看到了这一题，也发现不少人用模拟退火水过了，于是魔改我原题的程序，发现就是草不过，一直 92 ，又 WA 又 T，发现没前途。
那时候就康那些模拟退火过了的程序，发现都是一车面向数据特判。
他们是怎么知道数据的？小编非常疑惑。
于是我弃了这一题。
今天在翻我以前咕咕的题，发现了这一题，是个计算几何题，很有感觉。
于是想怎么做。
之前做过一道 CF 题，大概就是用了角前缀和的思想，发现这题取半径 =R 的时候也适用。
大概就是说有一个选定圆和一车圆（我们暂且把怪物看做半径为 0 的圆），求哪一个在选定圆上的点，被包含在其他圆中的次数最多。
来做这题的人肯定都会，就只要看一个非选定圆对选定圆上的哪段弧有贡献，前缀和一下就好了。
注意，要把自己建筑的圆的贡献设成无穷小，表示不能将其包含在内。
接下来我们考虑证明可能成为最大值的圆心位置的个数是只有严格 \Theta(n^2m) 的。
我们采取这样一种构造：一个点满足存在一个圆心为他的圆，与两个自己的建筑相切，并且也与一个怪物相切（前面已把其定义为圆）。
证明：如果不与怪物相切，那么圆还可以缩小。如果不与两个建筑相切，那么圆还可以放大。
于是圆心个数就被缩成 2\times 10^5 级别的，二分写的稳一点就可以过。
后面还要 \Theta(n+m) 判最大可行直径。
```cpp
#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;
}
```